perm filename ALLHEU.TEX[AM,DBL]3 blob
sn#400099 filedate 1978-12-06 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00028 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 \ASEC{HEURISTICS}
C00010 00003
C00017 00004 \ASSEC{Heuristics for dealing with Any-concept}
C00018 00005 \ASSSEC{Heuristics for any facet of Any-concept}
C00033 00006 \ASSSEC{Heuristics for the Examples facets of Any-concept}
C00067 00007 \ASSSEC{Heuristics for the Conjecs facet of Any-concept}
C00076 00008 \ASSSEC{Heuristics for the Analogies facet of Any-concept}
C00085 00009 \ASSSEC{Heuristics for the Genl/Spec facets of Any-concept}
C00115 00010 \ASSSEC{Heuristics for the View facet of Any-concept}
C00117 00011 \ASSSEC{Heuristics for the In-dom/ran-of facets of Any-concept}
C00120 00012 \ASSSEC{Heuristics for the Definition facet of Any-concept}
C00124 00013 \ASSEC{Heuristics for dealing with any Active concept}
C00141 00014 \ASSEC{Heuristics for dealing with any Predicate}
C00147 00015 \ASSEC{Heuristics for dealing with any Operation}
C00169 00016 \ASSEC{Heuristics for dealing with any Composition}
C00185 00017 \ASSEC{Heuristics for dealing with any Insertions}
C00186 00018 \ASSEC{Heuristics for dealing with the operation Coalesce}
C00194 00019 \ASSEC{Heuristics for dealing with the operation Canonize}
C00206 00020 \ASSEC{Heuristics for dealing with the operation Substitute}
C00210 00021 \ASSEC{Heuristics for dealing with the operation Restrict}
C00212 00022 \ASSEC{Heuristics for dealing with the operation Invert}
C00214 00023 \ASSEC{Heuristics for dealing with Logical combinations}
C00217 00024 \ASSEC{Heuristics for dealing with Struc\-tures}
C00221 00025 \ASSEC{Heuristics for dealing with Ordered-struc\-tures}
C00225 00026 \ASSEC{Heuristics for dealing with Unordered-struc\-tures}
C00226 00027 \ASSEC{Heuristics for dealing with Multiple-eles-struc\-tures}
C00227 00028 \ASSEC{Heuristics for dealing with Sets}
C00230 ENDMK
C⊗;
\ASEC{HEURISTICS}
\qq{Infallible rules of discovery leading to the solution of all possible
mathematical problems would be more desirable than the philosophers'
stone, vainly sought by the alchemists. Such rules would work magic;
but there is no such thing as magic. To find unfailing rules
applicable to all sorts of problems is an old philosophical dream;
but this dream will never be more than a dream.}{P\'olya}
\yyskip
\qq{To the extent that a professor of music at a conservatoire can assist
his students in becoming familiar with the patterns of harmony and
rhythm, and with how they combine, it must be possible to assist
students in becoming sensitive to patterns of reasoning and how they
combine. The analogy is not far-fetched at all}{Dijkstra}
\yyskip
This appendix lists all the heuristics with which AM is initially
provided. They are organized by concept, most general concepts
first. Within a concept, they are organized into four groups:
\yskip
\noindent $\bullet $ Fillin: rules for filling in new entries on various facets.
\noindent $\bullet $ Check: rules for patching up existing entries on various
facets.
\noindent $\bullet $ Suggest: rules which propose new tasks to break AM out of
stagnant loops.
\noindent $\bullet $ Interest: criteria for estimating the interestingness of
various entities.
\yskip
Each heuristic is presented in English translation. Whenever there is
a very tricky, non-obvious, or brilliant translation of some English
clause into LISP, a brief note will follow about how that is coded.
Also given (usually) are some example(s) of its use, and its overall
importance. Concepts which have no heuristics are not present in
this appendix.
All the heuristics in this appendix were used by AM; in
addition,
many heuristics were planned on paper but never coded (e.g.,
those dealing with proof techniques, those dealing with the drives
and rewards of generalized message senders/receivers), and whole
classes of rules were coded but never used by AM during any of its
runs (e.g., how to deal with contradictions, how to deal with Intu's
facets). Such superfluous rules will not be included here. They
would raise the total number of heuristic rules from 242 to
about 500.
The rule numbering in this Appendix is referred to occasionally
elsewhere. The total number of rules coded in AM is actually
higher, since many rules are present but never used, and since many
rules listed with one number here are really {\it several} rules in
LISP (e.g., see rules 35 and 188).
\eh
\bh
\hh If entity X is an example of concept C, and X satisfies some
features on C.Int,
Then X is interesting, and C's Interestingness features
will indicate a numeric rating for X.
\eh
This is practically the {\sl definiton} of the Int facet.
Below is a much more unusual rule:
\bh
\hh If entity X is an example of concept C, and X satisfies absolutely none of the
features on C.Int, and X is just about the only C which doesn't satisfy something,
Then X is interesting because of its unusual boringness.
\eh
Since most singletons are interesting because all pairs of their elements
are Equal, the above rule says it would be interesting actually to find a singleton
for which {\sl not} all pairs of its members were equal. While it would be interesting, AM has
very little chance of finding such a critter.
\ASSEC{Heuristics for dealing with Any-concept}
This concept has a huge number of heuristics. For that reason, I have partitioned
off --- both here and in AM itself\foo{
Thus the LISP program has a separate concept called ``Examples-of-any-concept",
another concept called ``Definitions-of-any-concept", etc.
} --- the heuristics which apply to each kind of facet.
\ASSSEC{Heuristics for any facet of Any-concept}
The first set of heuristics we'll look at is very general, applying to no
particular facet exclusively.
\hs{Any-concept}{Fillin}
\bh
\hh When trying to fill in facet F of concept C, for any C and F,
If C is analogous to concept X, and X.F has some entries,
Then try to construct the analogs of those entries, and see if they
are really valid entries for C.F.
\eh
Recall that ``C.F" is shorthand for ``facet F of concept C". This rule simply
says that if an analogy exists between two concepts C and X,
then it may be strong enough to map entries on X.F into entries for C.F.
Note that F can be any given facet.
There is an analogy between Sets and Bags, and AM uses the above rule to turn
the extreme example of Sets --- the empty set --- into the extreme kind of bag.
\hs{Any-concept}{Suggest}
\bh
\hh If the F facet of concept X is blank,
Then consider trying to fill it in.
\eh
The above ultra-weak rule will result in a new task being added to the agenda,
for every blank facet of every concept. It is more of a legal move generator
than a plausible move proposer.
The rating of each such task will depend on the Worth of the concept X and the
overall worth of the type F facet, but in all cases will be {\sl very small.}
The ``emptiness" of a facet is always a valid
reason for trying to fill it in,
but never an {\sl a priori} important reason.
So the net effect of the rule is to slightly bias AM toward working on blank
--- rather than non-blank --- facets.
\bh
\hh While trying to fill in facet F of concept C, for any C and F,
if C is known to be similar to some other concept D, except for difference d,
Then try to fill in C.F by selecting items from D.F for which d is nonexistent.
\eh
This rule is made more specific when F is actually known, and hence
the format of
d is actually determined. For example, if C=Reverse-at-all-levels, F=examples,
then (at one particular moment) a note is found on the Conjecs facet of
concept C which says that C is just like the concept D=Reverse-top-level,
except C also recurs on the nonatomic elements of its arguments, whereas D doesn't.
Thus d is made null by choosing examples of D for which there are no nonatomic
elements. So an example like \6``Reverse-top-level(<a b c>)=<c b a>''\0 will be
selected and will lead to the proposed example
\6``Reverse-at-all-levels(<a b c>)=<c b a>"\1, which is in fact valid.
\bh
\hh After dealing with concept C,
Slightly, temporarily boost
the priority value
of each existing task which involves an Active concept
whose domain or range is C.
\eh
This is done efficiently using the In-dom-of and In-ran-of facets of C.
A typical usage was after checking the just-filled-in
examples of Bags, when AM slightly
boosted the rating of filling in examples of Bag-union, and this task
just barely squeaked through as the next one to be chosen.
Note that the rule reinforced that task twice, since both domain and range
of Bag-union are bags.
\hs{Any-concept}{Check}
\bh
\hh When checking facet F of concept C, (for any F and C,)
Prune away at the entries there until the facet's size is reduced to
the size which C merits.
\eh
The algorithm for doing this is as follows: The Worth of C is multiplied by
the overall worth of facet type F. This is normalized in two ways, yielding
the maximum amount of list cells that C.F may occupy, and also yielding the
maximum number of separate entries to keep around on C.F. If either limit
is being exceeded, then an entry is plucked at random (but weighted to favor
selection from the rear of the facet) and excised. This repeats as long as
C.F is oversized. As space grows tight, the normalization weights decline,
so each concept's allocation is reduced.
\bh
\hh When checking facet F of concept C,
Eliminate redundant entries.
\eh
Although it might conceivably mean something for an entry to occur twice,
this was never desirable for the set of facets which each AM concept possessed.
\hs{Any-concept}{Interest}
The interest features apply to tell how interesting a concept is, and are
rarely subdivided by relevant facet. That is, most of the reasons that
Any concept might be interesting will be given below.
\bh
\hh A concept X is interesting if X.Conjecs contains some interesting entries.
\eh
\bh
\hh A concept is interesting if its boundary accidentally coincides with
another, well-known, interesting concept.
\eh
The boundary of a concept means the items which just barely fall into
(or just barely miss satisfying) the definition of that concept. Thus the
boundary of Primes might include 1,2,3,4.
If the boundary of Even numbers includes numbers differing by at most 1 from
an even number, then clearly their boundary is {\sl all} numbers. Thus it coincides
with the already-known concept Numbers, and this makes Even-nos more interesting.
This expresses the property we intuitively understand as: no number is very far
from an even number.
\bh
\hh A concept is interesting if its boundary accidentally coincides with
the boundary of another, very different, interesting concept.
\eh
Thus, for example, Primes and Numbers are both a little more interesting
since the extreme cases of numbers are all boundary cases of primes.
Even numbers and Odd numbers both have the same boundary, namely Numbers.
This is a tie between them, and slightly raises AM's interest in both concepts.
\bh
\hh A concept is interesting if it is --- accidentally --- precisely the
boundary of some other, interesting concept.
\eh
In the case mentioned for the above rule, Numbers is raised in interest
because it turns out to be the boundary for even and odd numbers.
\bh
\hh A concept is boring if, after several attempts, only a couple
examples are found.
\eh
Another rule indicates, in such situations, that the concept may be
forgotten and replaced by some conjecture.
\bh
\hh Concept C is interesting if some normally-inefficient operation F
can be efficiently performed on C's.
\eh
Thus it is very fast to perform Insert of items into lists because
(i) no pre-existence checking need be done (as with sets and osets),
and (ii) no ordered merging need be done (as with bags).
So ``Lists" is an interesting concept for that reason, according to the
above rule.
\bh
\hh Concept C is interesting if each example of C accidentally seems to
satisfy the otherwise-rarely satisfied predicate P, or (equivalently)
if there is an unusual conjecture involving C.
\eh
This is almost a primitive affirmation of intererestingness.
\bh
\hh Concept C is interesting if C is closely related to the very interesting
concept X.
\eh
This is intererestingness by association. AM was interested in
Divisors-of because it was closely related to TIMES, which had
proven to be a very interesting concept.
\bh
\hh Concept C is interesting if there is an analogy in which
C corresponds to Y, and the analogs of the Interest features of Y
indicate that C is interesting.
\eh
This might have been a very useful rule, if only there had been more
decent analogies floating around the system. As it was, the rule was
rarely used to advantage. It essentially says that the analogs of
Interest criteria are themselves (probably) valid criteria.
\bh
\hh A concept C is interesting if one of its generalizations or specializations
turns out to be unexpectedly very interesting.
\eh
``Unexpected" means that the interesting property hadn't already been observed for
C. If C is interesting in some way, and then one of its generalizations is
seen to be interesting
in exactly
the same way, then that is ``expected".
It's almost more interesting if the second concept unexpectedly {\sl lacks}
some fundamental property about C. At least in that case AM might learn something
about what gives C that property. In fact, AM has this rule:
\bh
\hh If concept C possesses some very interesting property lacked by one of its
specializations S,
Then both C and S become slightly more interesting.
\eh
In the LISP program, this is closely linked with rule 999.
\bh
\hh If a concept C is re-derived in a new way, that makes it more interesting.
If concepts C1 and C2 turn out to be equivalent concepts, then merge them.
The combined concept is now more interesting than either of its predecessors.
\eh
The two conditionals above are really the same rule, so they aren't given
separate numbers. C1 and C2 might be conjectured equivalent because their
examples coincide, each is a generalization of the other, their definitions
can be formally shown to be equivalent, etc.
This rule is similar in spirit to rule number 101.
\ASSSEC{Heuristics for the Examples facets of Any-concept}
The following heuristics are used for dealing with the many kinds of
examples facets which a concept can possess: non-examples, boundary
examples, Isa links, etc.
\hs{Any-concept . Examples}{Fillin}
\bh
\hh To fill in examples of X, where X is a kind of Y (for some more
general concept Y),
Inspect the examples of Y; some of them may be examples of X as well.
The further removed Y is from X, the less cost-effective this rule
is.
\eh
For the task of filling in Empty-struc\-tures, AM knows that concept is
a specialization of Struc\-tures, so it looks over all the then-known
examples of Struc\-tures. Sure enough, a few of them are empty (satisfy
Empty-struc\-tures.\-Defn). Similarly, for the task of filling in
examples of Primes, this rule would have AM notice that Primes is a
kind of Number, and therefore look over all the known examples of
Number. It would not be cost-effective to look for primes by testing
each example of Anything, and the third and final clause in the above
rule recognizes that fact.
\bh
\hh To fill in non-examples of concept X,
Search the specializations of X. Look at all their non-examples.
Some of them may turn out to be non-examples of X as well.
\eh
This rule is the counterpart of the last one, but for
{\it non}-examples. As expected, this was less useful than the
preceding positive rule.
\bh
\hh If the current task is to fill in examples of any concept X,
Then one way to get them is to symbolically instantiate a definition
of X.
\eh
That rule simply says to use some known tricks, some hacks, to wring
examples from a declarative definition. One trick AM knows about is
to plug already-known examples of X into the recursive step of a
definition. Another trick is simply to try to instantiate the base
step of a recursive definition. Another trick is to take a
definition of the form ``$\lambda $ (x) x isa P, and {\sl sub-expression}>",
work on instantiating just the \4sub-expression\1, and then pop back
up and see which of those items are P's.
\bh
\hh If the current task is to fill in non-examples of concept X,
Then one fast way to get them is to pick any random item, any example
of Anything, and check that it fails X.Defn.
\eh
This is an affirmation that for any concept X, most things in the
universe will probably not be X's. This rule was almost never used to
good advantage: non-examples of a concept X were never sought unless
there was some reason to expect that they might not exist. In those
cases, the presumption of the above rule was wrong, and it failed.
That is, the rule succeeded iff it was not needed.\foo{ Catch-22? }
\bh
\hh To fill in examples of concept X,
If X.View tells how to view a Z as if it were an X, and some examples
of Z are known,
Then just run X.View on those examples, and check that the results
really are X's.
\eh
Thus examples of osets were found by viewing other known examples of
struc\-tures (e.g., examples of sets) as if they were osets.
\bh
\hh To fill in examples of concept X,
Find an operation whose range is X,\foo{ or at least {\it intersects} X. Use
the In-ran-of facets and the rippling mechanism to find such an
operation. } and find examples of that operation being applied.
\eh
To fill in examples of Even-nos, this rule might have AM notice the
operation `Double'. Any example of Double will contain an example of
an even number as its value: e.g., <3$\→$6> contains the even number 6.
\bh
\hh If the current task is to fill in examples of concept X,
One bizarre way is to specialize X, adding a strong constraint to
X.Defn, and then look for examples of that new specialization.
\eh
Like the classical ``insane heuristic"\foo{ A harder task might be easier
to do. A stronger theorem might be easier to prove. This is called ``The Inventor's
Paradox", on page 121 of [P\'olya 57]. },
this sounds crazy but works embarassingly often. If I ask
you to find numbers having a prime number of divisors, the rate at
which you find them will probably be lower than if I'd asked you to
find numbers with precisely 2 divisors. The \4variety\0 of examples
will suffer, of course. The converse of this heuristic --- for
non-examples --- was deemed too unaesthetic to feed to AM.
\bh
\hh To fill in examples of X,
One inefficient method is to examine random examples of Anything,
checking each by running X.Defn to see if it is an X. Slightly
better is to ripple outward from X in all directions, testing all the
examples of the concepts encountered.
\eh
This is blind generate-and-test, and was (luckily) not needed much by
AM.
\bh
\hh To find more examples of X (or: to find an extreme example of X),
when a nice big example is known, and X has a recursive definition,
Try to plug the known example into the definition and produce a
simpler one. Repeat this until an example is produced which satisfies
the base-step predicate of the definition. That entity is then an
extreme (boundary) example of X.
\eh
For example, AM had a definition of a set as
\noindent ``Set.Defn $=↓{df}\ \lambda $ (S)
S=$\{\}$ or Set.Defn(Remove-random-element(S))." When AM found
the big example $\{A,B,\{\{C\},D\},\{\{\{E\}\}\},F\}$
by some other means, it used
the above rule and the recursive definition to turn this into
$\{A,B,\{\{\{E\}\}\},F\}$ by removing the randomly-chosen third element.
$\{A,B,F\}$ was produced next, followed by $\{B,F\}$ and $\{F\}$.
After that, $\{\}$
was produced and the rule relinquished control.
\bh
\hh To find examples of X, when X has a recursive definition,
One method with low success rate but high payoff is to try to invert
that definition, thereby creating a procedure for generating new
examples.
\eh
Using the previous example, AM was able to turn the recursive
definition of a set into the program ``Insert-any-random-item(S)",
which turns any set into a (usually different and larger) new set.
Since the rules which AM uses to do these transformations are very
special-purpose, they are not worth detailing here. This is one very
managable open problem, where someone might spend some months and
create a decent body of definition-inversion rules. A typical rule
AM has says:
\hjust to 270pt{``Any phrase matching `{\it Removing
an x and ensuring that P(x)}' can be
inverted and turned into this one: `{\it Finding any random x for which
P(x) holds, then inserting x'}."}
\noindent The class of definitions which can
be inverted using AM's existing rules is quite small; whenever AM
needed to be able to invert another particular definition, the author
simply supplied whatever rules would be required.
\bh
\hh While filling in examples of C,
if two constructs x and y are found which are very similar yet only
one of which is an example of the concept C,
Then one is a boundary example of C, and the other is a boundary
non-example,
and it's worth creating more boundary examples and boundary
non-examples by slowly transforming x and y into each other.
\eh
Thus when AM notices that $\{a\}$ and $\{a,b,a\}$ are similar yet not both
sets, it creates $\{a,b\},\ \{b,a\},\ \{a,a\}$ and sees which are and are not
examples of sets. In this way, some boundary items (both examples and
non-examples) are created. The rules for this slow transformation are
again special purpose. They examine the difference between the items
x and y, and suggest operators (e.g., Deletion) which will reduce
that difference. This GPS-like strategy has been well studied by
others, and its inferior implementation inside AM will not be
detailed.
\bh
\hh If the main task now is to fill in examples of concept C,
Consider all the examples of ``first cousins" of C. Some of them might
be examples of C as well.
\eh
By ``first cousins", we mean all direct specializations of all direct
generalizations of a concept, or vice versa. That is, going up once
along a Genl link, and then down once along a Spec link (or going
down one link and then up one link).
\bh
\hh If the main task now is to fill in boundary (non-)examples of
concept C,
Consider all the boundary (non-)examples of ``first cousins" of C.
Some of them might lie on the boundary of C as well.
\eh
If they turn out not to be boundary examples, they can be recorded as
boundary non-examples, and vice versa.
\bh
\hh To fill in Isa's links of concept X, (that is, to find a list of
concepts of which X is an example),
Just ripple down the tree of concepts, applying a definition of each
concept. Whenever a definition fails, don't waste time trying any of
its specializations. The Isa's of X are then all the concepts tried
whose definitions passed X.
\eh
When a new concept is created, e.g., a new composition, this rule can
ascertain the most specific Isa links that can be attached to it.
Another use for this rule would be: If the Isa link network ever got
fouled up (contained paradoxes), this rule could be used to
straighten everything out (with a logarithmic expenditure of time).
\hs{Any-concept . Examples}{Suggest}
\bh
\hh If some (but not most) examples of X are also examples of Y (for
some concept Y),
and some (but not most) examples of Y are also examples of X,
Then create a new concept defined as the intersection of those two
concepts (X $\inter $ Y). This will be a specialization of both concepts.
\eh
If you hapen to notice that some primes are palindromic, this rule
would suggest creating a brand new concept, defined as the set of
numbers which are both palindromic and prime. AM never actually
noticed this, since it represented all numbers in unary. If pushed,
AM will define Palindrome(n) to mean that the sequence of exponents
of prime factors is symmetric; thus
$2↑33↑85↑17↑111↑813↑3$ is palindromic in AM's sense
because the sequence of its exponents (3 8 1 1 8 3) is unchanged upon
reversal. In this sense, the only Prime palindromes are the primes
themselves (or: just `2', depending upon the precise definition).
\bh
\hh If very few examples of X are found,
Then add the following task to the agenda: ``Generalize the concept
X", for the following reason: ``X's are quite rare; a slightly less
restrictive concept might be more interesting".
\eh
Of course, AM contains a precise meaning for the phrase ``very few".
When AM looks for primes among examples of already-known kinds of
numbers, it will find dozens of non-examples for every example of a
prime it uncovers. ``Very few" is thus naturally implemented as a
statistical confidence level. AM uses this rule when very few
examples of Equality are found readily.
\bh
\hh If very many examples of X are found in a short period of time,
Then try to create a new, specialized version of X.
\eh
This is similar to the preceding rule. Since numbers are easy to
find, this might cause us to look for certain more interesting
subclasses of numbers to study.
\bh
\hh If there are no known examples for the interesting concept X,
Then consider spending some time looking for such examples.
\eh
I've heard of a math student who defined a set of number which had
quite marvelous properties. After the 20$↑{th}$ incredible theorem about
them he'd proved, someone noticed that the set was empty. The danger
of unwittingly dealing with a vacuous concept is even worse for a
machine than for a human mathematician. The above rule explicitly
prevents that.
\bh
\hh If the totality of examples of concept C is too small to be
interesting,
Then consider these reactions: (i) generalize C; (ii) forget C
completely; (iii) replace C by one conjecture.
\eh
This is a good example of when a task like \6``Fill in generalizations
of Numbers-with-1-divisors"\0 might get proposed with a
high-priority reason. The class of entities which C encompasses is
simply too small, too trivial to be worth maintaining a separate
concept. When C is numbers-with-1-divisor, C is really just another
disguise for the singleton set $\{1\}$. The above rule might cause a new
task to be added to the agenda, \6Fill in generalizations of
Numbers-with-1-divisor\1. When that task is executed, AM might
create the concept Numbers-with-odd-no-of-divisors,
Numbers-with-prime-number-of-divisors, etc. Besides generalizing
that concept, the above rule gives AM two other alternatives. AM may
simply obliterate the nearly-vacuous concept, perhaps leaving around
just the statement ``\41 is the only number with one divisor\1". That
conjecture might be tacked onto the Conjecs facet of Divisors-of. The
actual rule will specify criteria for deciding which of the three
alternatives to try. In fact, AM really starts all three activities:
a task will always be created and added to the agenda (to generalize
C), the vacuous concept will be tagged as ``forgettable", and AM will
attempt to formulate a conjecture (the only items satisfying C.Defn
are C.Exs).
\bh
\hh If the totality of examples of concept C is too large to be
interesting,
Then consider these three possible reactions: (i) specialize C; (ii)
forget C completely; (iii) replace C by one conjecture.
\eh
This is analogous to the preceding rule, but is used far less
frequently. One common use is when a disjunction of two concepts has
been formed which is accidentally large or already-known (e.g.,
``Evens $\union $ Odds" would be replaced by a conjecture).
\bh
\hh After filling in examples of C, if some examples were found,
Look at all the operations which can be applied to C's (that is,
access C.In-dom-of), find those which are interesting but which have
no known examples, and suggest that AM fill in examples for them,
because some items are now known which are in their domain, namely
C.Exs.
\eh
This rule had AM fill in examples of Set-insertion, as soon as some
examples of Sets had been found.
\bh
\hh After filling in examples of C, if some examples were found,
Consider the task of Checking the examples facet of concept C.
\eh
This was very frequently used during AM's runs.
\bh
\hh After checking examples of C, if many examples remain,
Consider the task of `Filling in some Conjecs for C'.
\eh
This was used often by AM. After checking the examples of C, AM would
try to empirically formulate some interesting conjecture about C.
\bh
\hh After successfully filling in non-examples of X, if no examples
exist,
If AM has not recently tried to find examples of X, then it should do
so.
If AM has recently tried and failed to find examples, consider the
conjecture that X is vacuous, empty, null, always-False. Consider
generalizing X.
\eh
\bh
\hh After trying in vain to find some non-examples of X, if many
examples exist,
Consider the conjecture that X is universal, always-True. Consider
specializing X.
\eh
\bh
\hh After successfully filling in examples of X, if no non-examples
exist,
If AM has not recently tried to find non-examples of X, then it
should consider doing so.
If AM has recently tried and failed to find non-examples, consider
the conjecture that X is universal, always-True. Consider
specializing X.
\eh
\bh
\hh After trying in vain to find some examples of X,
If many non-examples exist,
Consider the conjecture
that X is vacuous, null, empty, always-False. Consider generalizing X.
\eh
\hs{Any-concept . Examples}{Check}
\bh
\hh If the current task is to Check Examples of concept X,
and (Forsome Y) Y is a generalization of X with many examples,
and all examples of Y (ignoring boundary cases) are also examples of
X,
Then conjecture that X is really no more specialized than Y,
and Check the truth of this conjecture on boundary examples of Y,
and see whether Y might itself turn out to be no more specialized
than one of {\it its} generalizations.
\eh
This rule caused AM, while checking examples of odd-primes, to
conjecture that {\sl all} primes were odd-primes.
\bh
\hh If the current task is to Check Examples of concept X,
and (Forsome Y) Y is a specialization of X,
and all examples of X (ignoring boundary cases) are also examples of
Y,
Then conjecture that X is really no more general than Y,
and Check the truth of this conjecture on boundary examples of X,
and see whether Y might itself turn out to be no more general than
one of {\it its} specializations.
\eh
This rule is analogous to the preceding one for generalizations.
\bh
\hh When checking boundary examples of a concept C,
ensure that every scrap of C.Defn has been used.
\eh
It is often the tiny details in the definition that determine the
precise boundary. Thus we must look carefully to see whether Primes
allows 1 as an example or not. A definition like ``numbers divisible
only by 1 and themselves" includes 1, but this definition doesn't:
``numbers having precisely 2 divisors". In the LISP program, this
rule contains several hacks (tricks) for checking that the definition
has been stretched to the fullest. For example: if the definition is
of the form ``all x in X such that$\ldots $", then pay careful attention to
the boundary of X. That is, take the time to access X.Boundary-exs
and X.Boundary-non-exs, and check them against C.Defn.
\bh
\hh When checking examples of C,
Ensure that each example satisfies C.Defn, and each non-example fails
it. The precise member of C.Defn to use can be chosen depending on
the example.
\eh
As described earlier in the text, definitions can have descriptors
which indicate what kinds of arguments they might be best for, their
overall speed, etc.
\bh
\hh When checking examples of C,
If an entry e is rejected (i.e., it is seen to be not an example of C
after all), then remove e from C.Exs and consider inserting it on the
Boundary non-examples facet of C.
\eh
There is a complicated\foo{ Not necessarily sophisticated. First, AM
accesses the Worth of C. From this it determines how many boundary
non-examples C deserves to keep around (and how many total list cells
it merits). AM compares these quotas with the current number of (and
size of) entries already listed on C.bdy-non-exs. The degree of need
of another entry there then sets the ``odds" for insertion versus
forgetting. Finally a random number is computed, and the odds
determine what range it must lie in for e to be remembered. }
algorithm for deciding whether to forget e entirely or to keep it
around as a close but not close enough kind of example.
\bh
\hh When checking examples of C,
After an entry e has been verified as a bone fide example of C,
Check whether e is also a valid example of some direct specialization
of C.
If it is, then remove it from C.Exs, and consider adding it to the
examples facet of that specialization, and suggest the task of
Checking examples of that specialization.
\eh
\bh
\hh When checking examples of C,
If an entry e is rejected,
Then check whether e is nevertheless a valid example of some
generalization of C.
If it is, consider adding it to that concept's boundary-examples
facet, and consider adding it to the boundary non-examples facet of
C.
\eh
This is similar to the preceding rule.
\bh
\hh When checking non-examples of C, including boundary non-examples,
Ensure that each one fails a definition of C. Otherwise, transfer it
to the boundary examples facet of C.
\eh
\bh
\hh When checking non-examples of C, including boundary non-examples,
After an entry e has been verified as a bone fide non-example of C,
Check whether e is also a non-example of some direct generalization
of C.
If it is, then remove it from C.Non-Exs, and consider adding it to
the non-examples facet of that generalization, and suggest the task
of Checking examples of that generalization.
\eh
\bh
\hh When checking (boundary) non-examples of C,
If an entry e is rejected, that is if it turns out to be an example
of C after all,
Then check whether e is nevertheless a non-example of some
specialization of C.
If it is, consider adding it to that concept's boundary non-examples
facet.
\eh
This is similar to the preceding rule.
\ASSSEC{Heuristics for the Conjecs facet of Any-concept}
\hs{Any-concept . Conjecs}{Fillin}
When the task is to look around and find conjectures dealing with
concept C, the following general rules may be useful.
\bh
\hh If there is an analogy from X to C, and a nice item in X.Conjecs,
formulate and test the analogous conjecture for C.
\eh
Since an analogy is not much more than a set of substitutions,
formulating the `analogous conjecture' is almost a purely syntactic
transformation.
\bh
\hh Examine C.Exs for regularities.
\eh
What mysteries are lurking in the LISP code for \4this\0 rule, you
ask? Nothing but a few special-purpose hacks and a few ultra-general
hacks. Here is a slightly more specific rule for you seekers:
\bh
\hh Look at C.Exs. Pick one element at random. Write down statements
true about that example e. Include a list of all concepts of which it
is an example, all Interests features it satisfies, etc.
Then check each conjecture on this list against all other known
examples of C. If any example (except a boundary example) of C
violates a conjecture, discard it.
Take all the surviving conjectures, and eliminate any which trivally
follow from other ones.
\eh
This is a common way AM uses: induce a conjecture from one example
and test it on all the rest. A more sophisticated approach might be
to induce it by using a few examples simultaneously, but I haven't
thought of any nontrivial way to do that. The careful reader will
perceive that most of the conjectures AM will derive using this
heuristic will be of the form ``X is unexpectedly a specialization of
Y", or ``X is unexpectedly an example of Y", etc. Indeed, most of
AM's conjectures are really that simple syntactically.
\bh
\hh Formulate a parameterized conjecture, a ``template", which gets
slowly specialized or instantiated into a definite conjecture.
\eh
AM has only a few trivial methods for doing this (e.g., introduce a
variable initially and find the constant value to plug in there
later). As usual, they will be omitted here, and the author
encourages some research in this area, to turn out a decent set of
general rules for accomplishing this hypothesis template
instantiation. The best effort to date along these lines, in one
specific sophisticated scientific field, is that of META-DENDRAL
[Buchanan].
\hs{Any-concept . Conjecs}{Check}
\bh
\hh If a universal conjecture (For all X's, $\ldots $) is contradicted by
empirical data, gather the data together and try to find a regularity
in those exceptions.
If this succeeds, give the exceptions a name N (if they aren't
already a concept), and rephrase the conjecture (For all X's which
are not N's$\ldots $). Consider making X - N a new concept.
\eh
Again note how ``active" this little checking rule can be. It can
patch up nearly-true conjectures, examine data, define new concepts,
etc.
\bh
\hh After verifying a conjecture for concept C,
See if it also holds for related concepts (e.g., a generalization of
C).
\eh
There are of course bookeeping details not explicitly shown above,
which are present in the LISP program. For example, if conjecture X
is true for all specializations of C, then it must be added to
C.Conjecs and removed from the Conjecs facets of each specialization
of C.
\hs{Any-concept . Conjecs}{Suggest}
\bh
\hh If X is probably related to Y, but no definite connection is
known,
It's worthwhile looking for a specific conjecture tying X and Y
together.
\eh
How might AM know that X and Y are only {\sl probably} related? X and
Y may play the same role in an analogy (e.g., the singleton bag ``(T)"
and ``any typical singleton bag" share many properties), or they may
both be specializations of the same concept Z (e.g., two kinds of
numbers), or they may both have been created in the same unusual way
(e.g., Plus and Times and Exponentiation are all creatable by
\4repeating\0 another operation).
\hs{Any-concept . Conjecs}{Interest}
\bh
\hh A conjecture about X is interesting if X is very interesting.
\eh
\bh
\hh A nonconstructive existence conjecture is interesting.
\eh
Thus the unique factorization theorem is judged to be interesting
because it merely guarantees that some factoring will be into primes.
If you give an algorithm for that factoring, then the theorem
actually loses its mystique and (according to this rule) some of its
value. But it increases in value due to the next rule.
\bh
\hh A constructive existence conjecture is interesting if it is
frequently used.
\eh
\bh
\hh A conjecture C about X is interesting if the origin and the
verification of C for each specialization of X was quite independent
of each other, and preceded C's being noticed applicable to all X's.
\eh
This would be even more striking if \4proof\0 techniques were known,
and each specialized case had a separate kind of proof. Many number
theory results are like this, where there exists a general proof only
for numbers bigger than 317, say, and all smaller numbers are simply
checked individually to make sure they satisfy the conjecture.
Category theory is built upon practically nothing but this heuristic.
\ASSSEC{Heuristics for the Analogies facet of Any-concept}
\hs{Any-concept . Analogies}{Fillin}
\bh
\hh To fill in conjectures involving concept C, where C is analogous
to D,
Consider the analogue of each conjecture involving D.
\eh
\bh
\hh If the current task involves a specific analogy, and the request
is to find more conjectures,
Then consider the analog of each interesting conjecture about any
concept involved centrally in the analogy.
\eh
That is, this rule suggests applying the preceding rule to each
concept which is central to the given analogy. The result is a flood
of new conjectures. There is a tradeoff (explicitly taken into
account in the LISP version of this rule) between how interesting a
conjecture has to be, and how centrally a concept has to fit into the
analogy, in order to determine what resources AM should be willing to
expend to find the analogous conjecture. Note that this is not a
general suggestion of what to do, but a specific strategy for
enlarging the analogy itself. If the new conjecture is verified, then
not only would it be entered under some Conjecs facet, but it would
also go to enlarging the data struc\-ture which represents the analogy.
\bh
\hh Let the analogy suggest how to specialize and generalize each
concept into what is at least the analog of a known, very interesting
concept.
\eh
Like the last rule, this one simply says to use the analogy itself as
the ``reason" for exploring certain new entities, in this case new
concepts. When the Bags$↔$Numbers analogy is made, AM notices that
Singleton bags and Empty bags are two interesting, extreme
specializations of Bags. The above rule then allows AM to construct
and study what we know and love as the numbers one and zero. The
analogy is flawed because there is only one ``one", although there are
many different singleton bags. But just as singletons and empty bags
have special properties under bag operations, so do 0,1 under numeric
operations. This was one case where an analogy paid off handsomely.
\bh
\hh If it is desired to have an analogy between concepts X and Y, then
look for two already-known analogies between X$↔$Z and Z$↔$Y, for any Z.
If found, compose the two analogies and see if the resultant analogy
makes sense.
\eh
Since the analogies are really just substitutions, composing them has
a familiar, precise meaning. This rule was not used by AM during its
``good run", due to the paucity of analogies. The user can push AM into creating
more of them, and ultimately using this rule. A chain from X$↔$Z$↔$Y$↔$X
can be found which presents a new, bizarre analogy from X to itself.
\hs{Any-concept . Analogies}{Suggest}
\bh
\hh If an analogy is strong, and one concept has a very interesting
universal conjecture C (For all x in B$\ldots $), but the analog conjecture
\'C is false,
Then it's worth constructing the set of items in \'B for which the
conjecture holds. It's perhaps even more interesting to isolate the
set of exceptional elements.
\eh
With the Add$↔$Times analogy, it's true that all numbers n>1 can be
represented as the sum of two other numbers (each of them smaller
than n), but it is \4not\0 true that all numbers (with just a couple
exceptions) can be represented as the product of other (hence
smaller) numbers. The above rule has AM define the set of numbers
which can/can't be so represented. These are just the composite
numbers and the set of primes. This second way of encountering
primes was very unexpected --- both by AM and by the author. It
expresses the deep fact that one difference between Add and Times is
the presence of primes only for multiplication. At the time of its
discovery, AM didn't appreciate this fully of course.
\bh
\hh If space is tight, and no use of the analogy has ever been made,
and it is very old, and it takes up a lot of space,
Then it is permissable to forget it without a trace.
\eh
\bh
\hh If two valuable conjectures are syntactically identical, and can
be made identical by a simple substitution, then tentatively consider
the analogy which is that very substitution.
\eh
The associative/commutative property of Add and Times causes
them to be tied together in an analogy, because of this rule.
\bh
\hh If an analogy is very interesting and very complete,
Then spend some time refining it, looking for small exceptions. If
none are found, see whether the two situations are genuinely
isomorphic.
\eh
\bh
\hh If concepts X and Y are analogous, look for analogies between
their specializations, or between their generalizations.
\eh
This rule is not used much by AM, although the author thought it
would be.
\hs{Any-concept . Analogies}{Interest}
\bh
\hh An analogy which has no discrepancies whatsoever is not as
interesting as a slightly flawed analogy.
\eh
\bh
\hh An analogy is interesting if it associates (for the first time)
two concepts which are each unusally fully filled out (having many
conjectures, many examples, many interest features, etc.).
\eh
\ASSSEC{Heuristics for the Genl/Spec facets of Any-concept}
\hs{Any-concept . Genl/Spec}{Fillin}
\bh
\hh To fill in specializations of X, if it was very easy to find
examples of X,
Grab some features which would indicate than an X was interesting
(some entries from X.Interest, or more remote Interest predicates
garnered by rippling), and conjoin them onto the definition of X,
thereby creating a new concept.
\eh
Here's one instance where the above rule was used: It was so easy for
AM to produce examples of sets that it decided to specialize that
concept. The above rule then plucked the interestingness feature {\it ``all
pairs of members satisfy the same rare predicate"} and conjoined it to
the old definition of Sets. The new concept, Interesting-sets,
included all singletons (because all pairs of members drawn from a
singleton satisfy the predicate Equal) and empty sets.
\bh
\hh To fill in generalizations of concept X,
Take the definition $\Dscr $, and replace it by a generalization of $\Dscr $.
If $\Dscr $
is a concept, use $\Dscr $.Genl; if $\Dscr $ is a conjunction, then remove a
conjunct or generalize\foo{ i.e., recur. } a conjunct; if $\Dscr $ is a
disjunction, then add a disjunct or generalize a disjunct; if $\Dscr $ is
negated, then specialize the negate; if $\Dscr $ is an example of $\Delta $, then
replace $\Dscr $ by ``any example of $\Delta $"; if $\Dscr $
satisfies any property P, then
replace $\Dscr $ by ``anything satisfying P"; if $\Dscr $ is a constant\foo{ Of course
it's unlikely that a concept is defined simply as a constant, but the
preceding footnote shows that this little program can be entered
recursively, being fed a sub-expression of the definition. }, then
replace $\Dscr $ by a new variable (or an existing one) which could assume
value $\Dscr $; if $\Dscr $ is a variable, then enlarge its scope of possible
bindings.
\eh
This rule contains a bag of tricks for generalizing any LISP
predicate, the definition of any concept. They are all \4syntactic\0
tricks, however.
\bh
\hh To fill in generalizations of concept X, If some conjecture exists
about ``all X's and Y's" or ``in X or Y", for some other concept Y,
Create a new concept, a generalization of both X and Y, defined as
their disjunction.
\eh
This rule contains another trick for generalizing any concept,
although it is more meaningful, more semantic than the previous
rule's tricks. Many theorems are true about numbers with 1 or 2
divisors, so this might be one reasonable way to generalize
Numbers-with-1-divisor into a new useful\foo{ at least, several
theorems will be stated more concisely using this new concept:
Numbers with 1 or 2 divisors. } concept.
\bh
\hh To fill in generalizations of concept X,
If other generalizations G1, G2 of X exist but are {\it too} general,
Create a new concept, a generalization of X and a specialization of
both G1 and G2, defined as the conjunction of G1 and G2's
definitions.
\eh
Thus when AM generalizes Reverse-all-levels into Re\-verse-top-le\-vel
and Re\-verse-first-ele\-ment, the above rule causes AM to create a new
operation, which reverses the top level and which reverses the CAR\foo{
also the CAR of the CAR, etc., until a non-list is encountered. } of
the original list. While not particularly useful, the reader should
observe that it {\it is} midway in generality between the original
Reverse function and the first two generalizations.
\bh
\hh To fill in specializations of concept X,
Take the definition $\Dscr $ of X, and replace it by a specialization
of $\Dscr $. If $\Dscr $
is a concept, use $\Dscr $.Genl; if $\Dscr $ is a disjunction, then remove a
disjunct or specialize a disjunct; if $\Dscr $ is a conjunction, then add a
conjunct or specialize a conjunct; if $\Dscr $ is negated, then generalize
the negate; if $\Dscr $ is ``any example of $\Delta $", then replace
$\Dscr $ by a
particular example of $\Delta $;
if $\Dscr $ is ``anything satisfying $\Pscr $", then
replace $\Dscr $ by a particular satisfier of $\Pscr $;
if $\Dscr $ is a variable, then
replace it by a well-chosen constant or restrict its scope.
\eh
This rule contains a bag of tricks for specializing any LISP
predicate, the definition of any concept. They are all \4syntactic\0
tricks, however. Note that the Lisp code for this rule will typically
call itself (recur) in order to specialize small pieces of the
original definition.
\bh
\hh To fill in specializations of concept X, If some conjecture exists
about ``all X's which are also Y's" or ``in X and Y", for some other
concept Y,
Create a new concept, a specialization of both X and Y, defined as
their conjunction.
\eh
This rule contains another trick for specializing any concept,
although it is more meaningful, more semantic than the previous
rule's tricks. Many theorems about primes contain the condition
``p>2"; i.e., they are really true about primes which are odd. So this
might be one reasonable way to specialize Primes into a new concept:
by conjoining the definitions of Primes and Odd-numbers, into the new
concept Odd-primes. Here's another usage of this rule: If AM had
originally defined Primes to include `1', then the frequency of
conjectures where 1 was an exception would trigger this rule to
define Primes more normally ($p≥2$).
\bh
\hh To fill in specializations of concept X,
If other specializations S1, S2 of X exist but are {\it too} restrictive to
be interesting,
Create a new concept, a specialization of X and a generalization of
both S1 and S2, defined as the disjunction of S1 and S2's
definitions.
\eh
\bh
\hh To fill in generalizations of concept X, when a recursive
definition of X exists,
If the definition contains two conjoined recursive calls, replace
them by a disjunction or eliminate one call entirely.
If there is only one recursive call, disjoin a second call, this one
on a different destructive function applied to the original argument.
If the original destructive function is one of $\{CAR,CDR\},$ then let
the new one be the other member of that pair.
\eh
AM uses the first part of this rule to turn Equal-lists into two
variants of Same-length-as. The second part, while surprisingly
unused, could work on this definition of \it MEMBER:
``$\lambda $ (x,L) LISTP(L)
and: [x=CAR(L) or MEM\-BER(x,\-CDR(L))]"\1, which is just ``membership at
the top level of", or ``$\epsilon $", and transform it into this one of
{\it MEM}, which represents membership at \4any\0 depth: ``{\it
$\lambda $ (x,L)
LISTP\foo{ The Interlisp function LISTP(L) tests whether or not L is a
(nonnull) list. }(L) and: [x=CAR(L) or MEM(x,CDR(L)) or
MEM(x,CAR(L))]"}. The rule noticed a recursive call on CDR(L), and
simply disjoined a recursive call on CAR(L).
\bh
\hh To fill in specializations of concept X, when a recursive
definition of C exists,
If the definition contains two disjoined recursive calls, replace
them by a conjunction or eliminate one call entirely.
If there is only one recursive call, conjoin a second on another
destructive function applied to the original argument. Often the two
recursions will be on the CAR and the CDR of the original argument to
the predicate which is the definition for X.
\eh
This is closely related to the preceding rule. Just as it turned the
concept of `element of' into the more general one of `membership at
any depth', the above rule can specialize the definition of
{\it MEMBER} into this one, called {\it AMEM: ``$\lambda $ (x,L) LISTP(L) and:
[x=CAR(L) or: [AMEM(x,\-CDR(L)) and AMEM(x,\-CAR(L))]]"}.\foo{ This operation is
almost impossible to explain verbally. AMEM(x,L) means that x is an element of L,
and for each member M of L before the x, M is an ordered
struc\-ture and x is an element of M,
and for each member N of M before the x which is inside M,$\ldots $ etc.
For example,
<[x] [ {\2<} <x a b> <x> x d e{\2>} <x f> x g h ] [<x i> x j] x k [l] m>. }
\bh
\hh To fill in specializations of concept X,
Find, within a definition of X (at even parity of {\it NOT's}), an
expression of the form {\it ``For some x in X, P(x)"}, and replace it either
by {\it ``For all x in X, P(x)", \rm or by \it P(x$↓0$)}.
\eh
Thus ``sets, all pairs of whose members satisfy {\it some} interesting
predicate" gets specialized into ``sets, all pairs of whose members
satisfy Equality". The same rule, with ``even parity" replaced by
``odd parity", is useful for \4generalizing\0 a definition. This rule
is really 4 separate rules, in the LISP program. The same rule, with
the transformations going in the opposite direction, is also used for
generalizing. The same rule, with the transformations reversed and
the parity reversed, is used for specializing a definition. Here is
that doubly-switched rule:
\bh
\hh To fill in specializations of concept X,
Find within a definition of X (at odd parity of {\it NOT's}) an expression
of the form {\it ``For all x in X, P(x)"}, and replace it either by
{\it ``For some x in X, P(x)", \rm or by \it P(x$↓0$)}.
Or replace {\it ``P(c)"}, where {\it c}
is a constant, by {\it ``For some x in $\Cscr $, P(x)"} where
$\Cscr $ is a concept of
which {\it c} is one example.
\eh
\bh
\hh When creating in a specialization S of concept C,
Note that S.Genl should contain C, and that C.Spec should contain S.
\eh
The analogous rule exists, in which all spec and genl are switched.
\hs{Any-concept . Genl/Spec}{Suggest}
\bh
\hh After creating a new specialization S of concept C,
Explicitly look for ties between S and other known specializations of
C.
\eh
For example, after AM defines the new concept of
Numbers-with-3-divisors, it looks around for ties between that kind
of number and other kinds of numbers.
\bh
\hh After creating a new generalization G of concept C,
Explicitly look for ties between G and other close generalizations of
C.
\eh
For example, AM defined the new predicates Same-size-CARs and
Same-size-CDRs\foo{ Two lists satisfy Same-size-CDRs iff they have the
same number of members. Two lists satisfy Same-size-CARs iff (when
written out in standard LISP notation) they have the same number of
initial left parentheses and also have the same first identifier
following that last initial left parenthesis. } as two
generalizations of Equality. The above rule then suggested that AM
explicitly try to find some connection between these two new
predicates. Although \4AM\0 failed, Don Knuth (using a similar
heuristic, perhaps?) also looked for a connection, and found one: it
turns out that the two predicates are both ways of defining the
relation we intuitively understand as ``having the same length as".
\bh
\hh After creating a new specialization S of concept C,
Consider looking for examples of S.
\eh
This has to be said explicitly, because all too often a concept is
specialized into vacuousness.
\bh
\hh After creating a new generalization G of concept C,
Consider looking for non-examples of G.
\eh
This has to be said explicitly, because all too often a concept is
generalized into vacuous universality. This rule is less useful to AM
than the preceding one.
\bh
\hh If concept C possesses some very interesting property lacked by
one of its specializations S,
Then considering creating a concept intermediate in specialization
between C and S, and see whether that possesses the property.
\eh
This rule will trigger whenever a new generalization or
specialization is created.
\bh
\hh If concept S is now very interesting, and S was created as a
specialization of some earlier concept C,
Give extra consideration to special\-i\-zing S, and to special\-i\-zing
concept C again (but in different ways than ever before).
\eh
The next rule is the analog of the preceding one. They incorporate
tiny bits of the strategies of hill-climbing and learning from one's
successes.
\bh
\hh If concept G is now very interesting, and G was created as a
generalization of some earlier concept C,
Give extra consideration to general\-i\-zing G, and to gene\-ral\-i\-zing C in
other ways.
\eh
The analogous rules exist, for concepts that have become so boring
they've just been discarded:
\bh
\hh If concept X proved to be a dead-end, and X was created as a
generalization of (specialization of) some earlier concept C,
Give less consideration to gene\-ral\-i\-zing (spe\-cial\-i\-zing) X, and to
gene\-ral\-i\-zing (spe\-cial\-i\-zing) C in other ways in the future.
\eh
\hs{Any-concept . Genl/Spec}{Check}
\bh
\hh When checking a generalization G of concept C,
Specifically test to ensure that G is not equivalent to C.
The easiest way is to examine the non-examples (especially boundary
non-examples) of C, and look for one satisfying G; or examine the
examples of G (esp. boundary) and look for one failing to satisfy C.
If they appear to be the same concept, look carefully at G. Are there
any specializations of G whose examples have never been filled in? If
so, then by all means suggest looking for such concepts' examples
before concluding that G and C are really equivalent.
If they are the same, then replace one by a conjecture.
If they are different, make sure that some boundary non-example of C
(which is an example of G) is explicitly stored for C.
\eh
This rule makes sure that AM is not deluding itself. When AM
generalizes Numbers-with-1-divisor into
Numbers-which-equal-their-no-of-divisors, it still hasn't gotten past
the singleton set $\{1\}$. The conjecture in this case would be ``\4The
only number which equals its own number of divisors is 1\1".
Typically, when a generalization G of C turns out to be equivalent to
C, there is theorem lurking around, of the form ``All G's also satisfy
this property$\ldots $", where the property is the ``extra" constraint
present in C's definition but absent from G's. This rule also was
used when AM had just found some examples of Sets. AM almost believed
that all Unordered-Struc\-tures were also Sets, but the last main
clause of the rule had AM notice that Bags is a specialization of
Unordered-struc\-tures, and that the latter concept had never had any
of its examples filled in. As a result, AM printed out this message:
``Almost concluded that Unordered-struc\-tures are also always Sets.
But will wait until examples of Bags are found. Perhaps some Bags
will not be Sets." In fact, examples of Bags are soon found, and they
aren't sets.
\bh
\hh When checking a specialization S of concept C,
Specifically test to ensure that S is not equivalent to C.
If they are the same, then replace one by a conjecture.
If they are different, make sure that some boundary example of C
(which is not an example of S) is explicitly stored for C.
\eh
This rule is similar to the preceding one. If adding a new constraint
P to the definition doesn't change the concept C, then there is
probably a theorem there of the form ``All C's also satisfy constraint
P".
\bh
\hh When checking a specialization S of a specialization X of a
concept C,
if there exist other specs. of specs. of C,
then ensure that none of them are the same as S. This is especially
worthwhile if the specializing operators in each case were the same
but reversed in order.
\eh
Thus we can add a constraint to C and collapse the first two
arguments, or we can collapse the arguments and add the constraint;
either way, we get to the same very specialized new concept. The
above rule helps detect those accidental duplicates. E.g.,
Coalesced-\ Dom=Ran-\ Compositions are really the same as
Dom=Ran-\ Coalesced-\ Compositions, and this rule would suspect that they
might be.
\bh
\hh When checking the Genl or Spec facet entries for concept C,
ensure that C.Genl and C.Spec have no common member Z. If they do,
then conjecture that C and Z are actually equivalent.
\eh
In fact, this rule actually ensures that Generalizations(C) does not
intersect Specializations(C). If it does, a whole `cycle' of concepts
exists which can be collapsed into one single concept. See also rule
122, below.
\hs{Any-concept . Genl/Spec}{Interest}
\bh
\hh A generalization of X is interesting if all the previously-known
boundary non-examples are now boundary examples of the concept.
\eh
A check is included here to ensure that the new concept was not
simply defined as the closure of the old one.
\bh
\hh A specialization of X is interesting if all the previously-known
boundary examples are now boundary non-examples of the new
specialized concept.
\eh
A check is included here to ensure that the new concept was not
simply defined as the interior of the old one.
\bh
\hh If C$↓1$ is a generalization of C$↓2$, which is a generalization of
C$↓3$,$\ldots $, which is a generalization of C$↓j$, and it has just been learned
that C$↓j$ is a generalization of C$↓1$,
Then all the concepts C$↓1$,$\ldots $,C$↓j$ are equivalent, and can be merged,
and the combined concept will be much more interesting than any
single one, and the interestingness of the new composite concept
increases rapidly with {\it j}.
\eh
The Lisp code has the new interest value be computed as the maximum
value of the old concepts, plus a bonus which increases like the
square of {\it j}. This is similar to rule number 222. A rule
just like the preceding one exists, with `Specialization' substituted
everywhere for `Generalization'. Thus a closed loop of Spec links
constitutes a demonstration that all the concepts in that loop are
equivalent. These rules were used more frequently than expected.
\ASSSEC{Heuristics for the View facet of Any-concept}
\hs{Any-concept . View}{Fillin}
\bh
\hh To fill in View facet entries for X,
Find an interesting operation F whose range is X,
and indicate that any member of Domain(F) can be viewed as an X just by
running F on it.
\eh
While trying to fill in the View facet of Even-nos, AM used this rule. It
located the operation Doubling, whose domain is Numbers and whose range is
Even-nos. Then the rule created a new entry: ``to view any number as if it were
an even number, double it". This is a twisted affirmation of the standard
correspondence
between natural numbers and even natural numbers.
\ASSSEC{Heuristics for the In-dom/ran-of facets of Any-concept}
\hs{Any-concept . In-dom-of/In-ran-of}{Fillin}
\bh
\hh To fill in entries for the In-dom-of facet of concept X,
Ripple down the tree of concepts, starting at Active, to empirically
determine which active concepts can be run on X's.
\eh
This can usually be decided by inspecting the Domain/range facets of
the Active concepts. Occasionally, AM must actually try to run an
active $\Fscr $ on sample X's, to see whether it fails or returns a value.\foo{
One key feature of Lisp which permits this to be done is the Errorset
feature. }
\bh
\hh To fill in the In-ran-of facet of concept X,
Ripple down the tree of concepts, starting at Active, to empirically
determine which active concepts can be run to yield X's.
\eh
This can usually be decided by inspecting the Domain/range facets of
the Active concepts. Occasionally, AM inspects known examples of some
Active concept, to see if any of the results are X's.
\bh
\hh While filling in entries for the In-dom-of facet of X,
Look especially carefully for Operations which transform examples and
non-examples into each other;
This is even better if the operation pushes boundary exs/non-exs
`across the boundary'.
\eh
This was used to note that Insert and Delete had a lot to do with the
concept of Singleton.
\ASSSEC{Heuristics for the Definition facet of Any-concept}
\hs{Any-concept . Defn}{Suggest}
\bh
\hh If there are no known definitions for concept X,
Then it is crucial that AM spend some time looking for such
definitions.
\eh
This situation might occur if only an Algorithm is present for some
concept. In that case, the above rule would suggest a new,
high-priority task, and AM would then twist the algorithm into a
(probably very inefficient) definition. A much more serious
situation would occur if a concept were specified only by its
Intuition entries (created, e.g., by modifying another concept's
intuitions). In that case, rapidly formulating a precise definition
would be a necessity. Of course, this need never arose, since all
the intuitions were deleted.
\hs{Any-concept . Defn}{Check}
\bh
\hh When checking the Definition facet of concept C,
ensure that each member of C.Exs satisfies all definitions present,
and each non-example fails all definitions. If there is one
dissenting definition, modify it, and move the offending example to
the boundary.
\eh
There is little real ``checking" that can be done to a definition,
aside from internal consistency: If there exist several
suposedly-equivalent definitions, then AM can at least ensure they
agree on the known examples and non-examples of the concept. If the
Intuitions facets were permitted, then each definition could be
checked for intuitive appeal (i.e., consistency with some Intuition).
\bh
\hh When checking the Definition facet of concept C,
Try to find and eliminate any redundant constraints, try to find and
eliminate any circularity, check that any recursion will terminate.
\eh
Here are the other few tricks that AM knows for ``checking" a
definition. For each clause in the rule above, AM has a very limited
ability to detect and patch up ``bugs" of that sort. Checking that
recursion will terminate, for example, is done by examining the
argument to the recursive call, and verifying that it contains (at
some level before the original argument) an application of a LISP
function on Destructive-LISP-functions-list. There is no intelligent
inference that is going on here, and for that reason the process is
not even mentioned within the body of this document.
\ASSEC{Heuristics for dealing with any Active concept}
All the rules below are applicable to tasks which involve operations,
predicates, relations, functions, etc. In short, they apply to all
the concepts AM knows about which involve \4doing\0 something, which
involve action.
\hs{Active}{Fillin}
\bh
\hh If the current task is to fill in examples of the activity F,
One way to get them is to run F on randomly chosen examples of the
domain of F.
\eh
Thus, to find examples of Equality, AM repeatedly executed
Equality.Alg on randomly chosen pairs of objects. AM found examples
of Compositions by actually picking a pair of operations at random
and trying to compose them. Of course, most such ``unmotivated"
compositions turned out to be uninteresting.
\bh
\hh While filling in examples of the activity F, by running F.Algs on
random arguments from F.Domain,
It is worth the effort to specifically include extreme or boundary
examples of the domain of F, among the arguments on which F.Algs is
run.
\eh
\bh
\hh To fill in a Domain entry for active concept F,
Run F on various entities, rippling down the tree of concepts, to
determine empirically where F seems to be defined.
\eh
This may shock the reader, as it sounds dumb and explosive, but the
concepts are arranged in a tree (using Genl links), so the search is
really quite fast. Although this rule is rarely used, it always
seems to give surprisingly good results.
\bh
\hh To fill in generalizations of active F,
Consider just extending F, by enlarging its domain. Revise F.Defn as
little as possible.
\eh
Although Equality is initially only for struc\-tures, AM extends it
(using the same definition, actually) to a predicate over all pairs
of entities.
\bh
\hh To fill in specializations of active F,
Consider just restricting F, by shrinking its domain. Check F.Defn to
see if some optimization is possible.
\eh
\bh
\hh After an algorithm is known for F, if AM wants a better one,
AM is permitted to ask the user to provide a fast but opaque
algorithm for F.
\eh
This was used a few times, especially for inverse functions. A
nontrivial open-ended research problem (*)\foo{ Following Knuth, we
shall reserve a star {\bf (*)} for those problems which are quite
difficult, which should take the reader roughly three full lifetimes to
master. Readers not believing in reincarnation should therefore skip
such problems. } \1is to collect a body of rules which transform an
inefficient algorithm into a computationally acceptable one.
\bh
\hh If the current task is to fill in boundary (non-)examples of the
activity F,
One way to get them is to run F on randomly chosen boundary examples
and (with proper safeguards) boundary non-examples of the domain of
F.
\eh
Proper safeguards are required to ensure that F.Algs doesn't loop or
cause an error when fed a slightly-wrong (slightly-illegal) argument.
In LISP, a timer and an ERRORSET suffice as crude safeguards.
\bh
\hh If the current task is to fill in (boundary) non-examples of the
activity F,
One low-interest way to get them is to run F on randomly chosen
examples of its domain, and then replace the value obtained by some
other (very similar) value. Also, be sure to check that the
resultant i/o pair doesn't accidentally satisfy F.Defn.
\eh
The parentheses in the above rule mean that it is really two rules:
for \4boundary\0 non-examples, just change the final value slightly.
For \4typical\0 non-examples, change the result significantly. If
you read the words inside in the parentheses in the IF part, then
read the words inside the parentheses in the THEN part as well;
or else \4omit\0 them in both cases.
\hs{Active}{Check}
\bh
\hh When checking an algorithm for active F,
run that algorithm and ensure that the input/output satisfy F.Defn.
\eh
\bh
\hh When checking a definition $\Dscr $ for active concept F,
Run one of its algorithms and ensure that the input/output satisfy $\Dscr $.
\eh
This is the converse of the preceding rule. They simply say that the
definition and algorithm facets must be mutually consistent.
\bh
\hh While checking examples or boundary examples of the active concept
F,
Ensure that each input/output pair is consistent with F.Dom/range.
\eh
If the domain/range entry is <D$↓1$ D$↓2\ldots $ D$↓k\ \→$ R>,
and the i/o pair is <d$↓1$ d$↓2\ldots $ d$↓k$ , r>, then
each component d$↓i$ of the input must be an
example of the corresponding D$↓i$, and the output r must be an example
of R.
\bh
\hh When checking examples of the active concept F,
If any argument(s) to F were concepts, tag their In-domain-of facets
with `F'.
If any values produced by F are concepts, tag their In-range-of
facets with `F'.
\eh
For example, Restrict(Union) produced Add, at one time in AM's
history. Then the above rule caused `Restrict' to be inserted as a
new entry on Union.In-dom-of and also on Add.In-ran-of.
\hs{Active}{Suggest}
\bh
\hh If there are no known algorithms for active concept F,
Then AM should spend some time looking for such algorithms.
\eh
This situation might occur if only a Definition is present for some
operation. In that case, the above rule would suggest a new,
high-priority task, and AM would then twist the definition into a
(probably very inefficient) algorithm. The rule below is similar,
for the Domain/range facet:
\bh
\hh If the Domain/range facet of active concept F is blank,
Then AM should spend some time looking for specifications of F's
domain and range.
\eh
\bh
\hh If a Domain of active concept F is encountered frequently, either
within conjectures or as the domain or range of other operations and
predicates,
Then define that Domain as a separate concept, and raise the Worth of
F slightly.
\eh
The `Domain' here refers to the sequence of components, whose
Cartesian product is what is normally referred to in mathematics as
the {\sl domain} of the operation. This led to the definition of
``Anything $\times $ Struc\-tures", which is the domain of several Insertion
and Deletion operations, Membership testing predicates, etc.
\bh
\hh It is worthwhile to explicitly calculate the value of F for all
distinguished (extreme, boundary, interesting) members of and subsets
of its domain.
\eh
\bh
\hh If some domain component of F has a very interesting
specialization,
Then consider restricting F (along that component) to that smaller
domain.
\eh
Note that these last couple rules deal with the image of interesting
domain items. The next rule deals with the inverse image (pre-image)
of unusual range items. We saw earlier in this document (Chapter 2)
how this rule led to the definition of Prime numbers.
\bh
\hh If the range of F contains interesting items, or an interesting
specialization,
Then it is worthwhile to consider their inverse image under F.
\eh
\bh
\hh When trying to fill in new Algorithms for Active concept F,
Try to transform any conjectures about F into (pieces of) new
algorithms.
\eh
This is one place where a sophisticated body of transformation rules
might be inserted. Others are working on this problem [Burstall &
Darlington 75], and AM only contains a few simple tricks for turning
conjectures into procedures. For example, ``All primes are odd,
except `2' ", is transformed into a more eficient search for primes: a
separate test for x=2, followed by a search through only Odd-numbers.
\bh
\hh After trying in vain to fill in examples of active concept F,
Locate the domain of F, and suggest that AM try to fill in examples
for each component of that domain.
\eh
Thus after failing to find examples for Set-union, AM was told to
find examples of Sets, because that could have let the previous task
succeed. There is no recursion here: after the sets are found, AM
will not automatically go back to finding examples of Set-union. In
practice, that task was eventually proposed and chosen again, and
succeeded this time.
\bh
\hh After working on an Active concept F,
Give a slight, ephemeral boost to tasks involving Domain(F): give a
moderate size boost to each task which asks to fill in examples of
that domain/range component, and give a very tiny boost to each other
task mentioning such a concept.
\eh
This is both a supplement to the more general ``focus of attention"
rule, and a nontrivial heuristic for finding valuable new tasks. It
is the partial converse of rule 72.
\hs{Active}{Interest}
\bh
\hh An active concept F is interesting if there are other operations
with the same domain as F, and if they are (on the average) fairly
interesting. If the other operations' domain is only similar, then
they must be {\it very} interesting and have some valuable conjectures tied
to them, if they are to be allowed to push up F's interestingness
rating.
\eh
The value of having the same domain/range is the ability to compose
with them. If the domain/range is only similar, then AM can hope for
analogies or for partial compositions.
\bh
\hh An active concept is interesting if it was recently created.
\eh
This is a slight extra boost given to each new operation, predicate,
etc. This bonus decays rapidly with time, and thus so will the
overall worth of the concept, unless some interesting property is
encountered quickly.
\bh
\hh An active concept is interesting if its domain is very
interesting.
\eh
An important common case of this rule is when the domain is
interesting because all its members are equal to each other. The
corresponding statement about \4ranges\0 does exist, but only
operations can be said to have a specific range (not, e.g.
Predicates). Therefore, the `range' rule is listed under
Operation.Interest, as rule number 111.
\ASSEC{Heuristics for dealing with any Predicate}
Each of these heuristics can be assumed to be prefaced by a clause of
the form {\it ``If the current task is to deal with concept X, where X isa
Predicate,$\ldots $"}. This will be repeated below, for each rule.
\hs{Predicate}{Fillin}
\bh
\hh If the current task was (Fill-in examples of X),
and X is a predicate,
and more than 100 items are known in the domain of X,
and at least 10 cpu seconds were spent trying to randomly instantiate
X,
and the ratio of successes/failures is both >0 and less than .05
\yskip
Then add the following task to the agenda: (Fill-in generalizations
of X), for the following reason:
``X is rarely satisfied; a slightly less restrictive concept might be
more interesting".
This reason's rating is computed as three times the ratio of
nonexamples/examples found.
\eh
This rule says to generalize a predicate if it rarely succeeds
(rarely returns T). One use for this was when Equality was found to be
quite rare; the resultant generalizations did indeed turn out to be
more valuable (namely, ``numbers"). A similar use was found for predicates
which tested for identical equality of two angles, of two triangles,
and of two lines. Their generalizations were also valuable
(congruence, similarity, parallel, equal-measure). Most rules in
this appendix are not presented with the same level of detail as the
preceding one, as the reader has no doubt observed.
\bh
\hh To fill in Domain/range entries for predicate P,
P can operate on the domain of any specialization of P,
P can operate on any specialization of the domain of P,
P can operate on some restriction of the domain of any generalization
of P,
P may be able to operate on some enlargement of its current domain,
The range of P will necessarily be the doubleton set $\{T,F\}$,
P is guaranteed return T if any of its specializations do, and F if
any of its generalizations do.
\eh
This contains a compiled version of what we mean when we say that one
predicate is a generalization or specialization of another. Viewed as
relations, as subsets of a Cartesian product of spaces, this notion
of general/special is just that of superset/subset. The last line of
the rule is meant to indicate that adding new constraints onto P can
only make it return True less frequently, while relaxing P's
definition can only make it return True more often.
\hs{Predicate}{Suggest}
\bh
\hh If all the values of Active concept $\Fscr $ happen to be Truth-values,
and $\Fscr $ is not known to be a predicate,
Then conjecture that $\Fscr $ is in fact a predicate.
\eh
This rule is placed on the Suggest facet because, if placed anywhere
else on this concept, it could only be seen as relevant by AM if AM
already knew that $\Fscr $ were a predicate. On the other hand, the rule
can't be placed, e.g., on Active.Fillin, since just forgetting
(deleting) this ``Predicate" concept should be enough to delete all
references to predicates anywhere in the system.
\hs{Predicate}{Interest}
\bh
\hh A predicate $\Pscr $ is interesting if its domain is Any-concept (the
collection of all known concepts). This is especially true if there is a
significant positive correlation (theoretical or empirical) between
concepts' worths and their $\Pscr $-values.
\eh
This very high level heuristic wasn't used by AM during its
``good" run (the one chronicled in Section 6.2.1).
\ASSEC{Heuristics for dealing with any Operation}
\hs{Operation}{Fillin}
\bh
\hh To fill in examples of operation F (with domain A and range B),
when many examples $\alpha $ of A are already known,
and F maps some of those examples $\alpha $ into distinguished members (esp:
extrema) b of B,
Then (for each such distinguished member ``b"$\epsilon \,$B)
study F\inv (b) as a
new concept. That is, isolate those members of A whose F-value is
the unusual item b$\epsilon $B.
\eh
This rule says to investigate the inverse image of an unusual item b,
under the interesting operation f. When b=2 and
f=number-of-divisors-of, this rule leads to the definition of {\it prime
numbers}. When b=$\phi $\foo{ the empty set, phi, NIL,
$\{\}$ } and f=Intersection,
the rule led to the discovery of the concept of {\it disjointness} of sets.
\bh
\hh To fill in Domain/range entries for operation F,
F can operate on the domain of any specialization of F,
F can operate on the specialization of the domain of any
specialization of F (including F itself),
F can operate on some restriction of the domain of any generalization
of F, at least on its current domain and perhaps even on a bigger
space,
F may be able to operate on some generalization of (some component(s)
of) its current domain,
F can only (and will always) produce values lying in the range of
each generalization of F,
F can --- with the proper arguments --- produce values lying in the
range of any particular specialization of F.
\eh
There are only a few changes between this rule and the corresponding
one for Predicates. Recall that Operations can be multi-valued, and
those values are not limited to the set $\{$T,F$\}$.
\bh
\hh To fill in Domain/range entries for operation F, when some exist
already,
Take an entry of the form <D$↓1$ D$↓2\ldots $ D$↓n\ \→$ R> and see
if D$↓i\times $R is
meaningful for some {\it i} (especially: {\it i=n}).
If so, then remove D$↓i$ from the left side of the entry, and replace R
by D$↓i\times $R, and modify the definition of F.
\eh
In LISP, ``meaningful" is coded as: either D$↓i\times $R is equivalent to
an already-known concept, or else it is found in at least two
interesting conjectures. This is probably an instance of what
McDermott calls natural stupidity\foo{ See [McDermott 76] for natural
stupidity. He criticizes the use of very intelligent-sounding names
for otherwise-simple program modules. But consider {\it ``Homo sapiens"},
which means ``wise man". Now {\it there's} a misleading label$\ldots $}. This
rule is tagged as being explosive, and is not used very often by AM.
\bh
\hh To fill in a Range entry for operation F,
Run F on various domain examples, especially boundary examples, to
collect examples of the range. Then ripple down the tree of concepts
to determine empirically where F seems to be sending its values.
\eh
This may shock the reader, as it sounds dumb and explosive, but the
concepts are arranged in a tree (using Genl links), so the search is
really quite fast. Although this rule is rarely used, it always
seems to give surprisingly good results.
\bh
\hh If operation F has just been applied, and has yielded a new concept
C as its result,
Then carefully examine F.Dom/range to try to find out what C.Isa
should be. C.Isa will be all legal entries listed as values of the
range of F.
\eh
When F=Compose, say AM has just created C=Empty$\circ$Insert.\foo{i.e.,
insert x into a struc\-ture S and then see if S is empty. This leads AM
to realize that inserting can never result in an empty struc\-ture. }
What is C? It is a concept, of course, but what else? By examining
the Domain/range facet of Compose, AM finds the entry <Active Active
$\→$ Active>. Aha! So C must be an Active. But AM also finds the entry
<Predicate Active $\→$ Predicate>. Since ``Empty" is a predicate, the
final composition C must also be a predicate. So C.Isa would be
filled in with ``Predicate". AM thus used the above rule to determine
that Empty$\circ$Insert was a predicate. Even if this rule were excised,
AM could still determine that fact, painfully, by noticing that all
the values were truth-values.
\bh
\hh If operation F has just been applied to A$↓1$,A$↓2,\ldots $, and has yielded
a new concept C as its result,
Then add F to C.In-ran-of; add F to the In-dom-of facet of all the
A$↓i$'s which are concepts; add <A$↓1 \ldots \ \→$ C> to F.Exs.
\eh
There is some overlap here with earlier rules, but there is no
theoretical or practical difficulty with such redundancy.
\bh
\hh When filling in examples of operation F, if F takes some existing
concepts A$↓1$, A$↓2, \ldots $ and (may) produce a new concept,
Then only consider, as potential A$↓i$'s, those concepts which already
have some examples. Prefer the A$↓i$'s to be interesting, to have a
high worth rating, to have some interesting conjectures about them,
to have several examples and several non-examples, etc.
\eh
The danger here is of, e.g., Composing two operations which turn out
to be vacuous, or of Conjoining an empty concept onto another, or of
proliferating variants of a boring concept, etc.
\hs{Operation}{Check}
Below are rules used to check existing entries on various facets of
operations.
\bh
\hh To check the domain/range entries on the operation F,
IF a domain/range entry has the form (D D D$\ldots \ \→$ R),
and all the D's are equal, and R is a generalization of D (or, with
less enthusiasm: if R and D have a significant overlap),
THEN it's worth seeing whether (D D D$\ldots \ \→$ D) is consistent with all
known examples of the operation:
If there are no known examples, add a task to the agenda re\-quest\-ing
they be filled in.
If there are examples, and (D D D$\ldots \ \→$ D) is consistent, add it to
the Do\-main/\-range facet of this operation.
If there are some contradicting examples, create a new concept which
is defined as this operation restricted to (D D D$\ldots \ \→$ D).
\eh
When AM restricts Bag-union to numbers (bags of T's), the new
operation has a Domain/range entry of the form (Numbers Numbers $\→$
Bag). The above rule has AM investigate whether the range
specification mightn't also be narrowed down to Number. In this case
it is a great help. The rule often fails, of course: the sum of two
primes is rarely a prime, the Cartesian product of two lists-of-atoms is
not a list-of-atoms, etc. Since this rule is almost instantaneous to
execute, it's cost-effective overall.
\bh
\hh When checking the domain/range entries on the operation F,
IF a domain/range entry has the form (D D D$\ldots \ \→$ R),
and all the D's are equal, and R is a specialization of D,
THEN it's worth inserting (D D D$\ldots \ \→$ D) as a new entry on F.Dom/ran,
even though that is redundant.
\eh
This shows that symmetry and aesthetics are sometimes preferable to
absolute optimization. That's why we program in Lisp, instead of
machine language. On the other hand, this rule wasn't really that
useful to AM. Now, by analogy,$\ldots $?
\bh
\hh When checking the Domain/range entries for operation F,
Ensure that the boundary items in the range can actually be reached
by F. If not, see whether the range is really just some known
specialization of F.
\eh
This rule is a typical checking rule. Note that it is active, not
passive: it might alter the Domain/range facet of F, it it finds an
error there.
\bh
\hh When checking examples of the operation F, for each such example,
If the value returned by F is a concept C, add `F' to C.In-range-of.
\eh
\hs{Operation}{Suggest}
\bh
\hh Whenever the domain of operation F has changed,
check whether the range has also changed. Often the range will change
analogously to the domain, where the operation itself is the Analogy.
\eh
\bh
\hh After working on Operation F,
Give a slight, ephemeral boost to tasks involving Range(F).
\eh
This wll be a moderate size boost for each task which asks to fill in
examples of that range concept, and a very tiny boost for each other
task mentioning such a concept. This is both a supplement to the
more general ``focus of attention" rule, and a nontrivial heuristic
for finding valuable new tasks. It is an extension of rule number
99, and a partial converse to rule 88.
\hs{Operation}{Interest}
\bh
\hh An operation F is interesting if there are other operations with
the same domain and range, and if they are (on the average) fairly
interesting.
\eh
\bh
\hh An operation F is interesting if it is the first operation
connecting its domain concept to its range concept, and if those
domain/range components are themselves valuable concepts, and there
is no analogy between them, and there are some interesting
conjectures involving the domain of F.
\eh
The above two rules say that F can be valuable becuase it's similar
to other, already-liked operations, or because it is totally
different from any known operation. Although these two criteria are
nonintersecting, their union represents only a small fraction of the
operations that get created: typically, \4neither\0 rule will
trigger.
\bh
\hh An operation F is interesting if its range is very interesting.
\eh
Range here refers to the concept in which all results of F must lie.
It is the R in the domain/range facet entry <D $\→$ R> for concept F.
The corresponding rule for `domains' is applicable to any Active, not
just to Operations, hence is listed under Active.Interest, as rule
number 22.
\bh
\hh An operation F is interesting if the values of F satisfy some
unusual property which is not (in general) satisfied by the arguments
to F.
\eh
Thus doubling is interesting because it always returns an even
number. This is one case where the interesting property can be
deduced trivially just by looking at the domain and range of the
operation: Numbers$\→$Even-nos.
\bh
\hh An operation is interesting if its values are interesting.
\eh
This can mean that each value is interesting (e.g., Compose is
well-received because it produces many new, valuable concepts as its
values). Or, it can mean that the operations' values, gathered
together into one big set, are interesting as a set. Unlike the
preceding rule, this one has no mention whatsoever of the domain
items, the arguments to the operation. This rule was used to good
advantage frequently by AM. For example, Factorings of numbers are
interesting because (using rule 122) for all x, Factorings(x)
is interesting in exactly the same way. Namely, Factorings(x),
viewed as a set, always contains precisely one item which has a
certain interesting property (see rule 225). Namely, all its
members are primes (see rule 122 again). This explains one way
in which AM noticed that all numbers seem to factor uniquely into
primes.
\bh
\hh An operation is interesting if its values are interesting,
ignoring the images of boundary items from the domain.
\eh
That is, if the image of the domain --- minus its boundary --- is
interesting.
\bh
\hh An operation is interesting if its values on the boundary items
from the domain are very interesting. Ignore the non-boundary parts
of the domain.
\eh
That is, if the image of the boundary of the domain is interesting.
\bh
\hh An operation is interesting if it leaves intact any interesting
properties of its argument(s). This is even better if it eliminates
some undesirable properties, or adds some new, desirable ones.
\eh
Thus a new, specialized kind of Insertion operation is interesting
if, even though it stuffs more items into a struc\-ture, the nice
properties of the struc\-ture remain. The operation ``Merge" is
interesting for this very reason: it inserts items into an
alphabetized list, yet it doesn't destroy that interesting property
of the list.
\bh
\hh An operation is interesting if its domain and range are equal. If
there is more than one domain component, then at least one of them
should equal the range. The more components which are equal to the
range, the better.
\eh
Thus ``Insertion" qualifies here, since its domain/range entry is
<Anything Struc\-tures $\→$ Struc\-tures>. But ``Union" is even better,
since {\it both} domain components equal the range, namely Struc\-tures.
\bh
\hh An operation is mildly interesting if its range is related somehow
(e.g. specialization of) to one or more components of its range. The
more the better.
\eh
A weakened form of the preceding rule.
\bh
\hh If the result of applying operation F is a new concept C,
Then the interestingness of F is weakly tied to that of C.
\eh
If the new concept C becomes very valuable, then F will rise slightly
in interest. If C is so bad it gets forgotten, F will not be
regarded quite as highly. When Canonize scores big its first time
used, it rises in interest. This caused AM to form poorly-motivated
canonizations, which led to dismal results, which gradually lowered
the rating of Canonize to where it was originally.
\ASSEC{Heuristics for dealing with any Composition}
\hs{Composition}{Fillin}
\bh
\hh To fill in algorithms for operation F, where F is a composition G$\circ$H,
One algorithm is: apply H and then apply G to the result.
\eh
Of course this rule is not much more than the definition of what it means
to compose two operations.
\bh
\hh To fill in Domain/range entries for operation F,
where F is a composition G$\circ$H,
Tentatively assume that the domain is Domain(H), and range is Range(G).
More precisely, the domain will be the result of substituting
Domain(H) for Range(H) wherever Range(H) appears (or: just once) in Domain(G).
\eh
Thus for F=Divides$\circ$Count, where Divides:<Number,Number $\→\ \{T,F\}$>, and
Count:<Bag $\→$ Number>, the above rule
would say that the domain/range entries for F are gotten by substituting
`Bag' for `Number' once or twice in Domain(Divides). The possible entries for
F.Dom/range are thus:
<Bag,Bag $\→\ \{T,F\}$>,
<Number,Bag $\→\ \{T,F\}$>,
and <Bag,Number $\→\ \{T,F\}$>.
\bh
\hh To fill in Domain/range entries for operation F, where F is a composition G$\circ$H,
But Range(H) does not occur as a component of Domain(G),
The range of F is still Range(G), but the domain of F is computed as follows:
Ascertain the component X of Domain(G) having the biggest (fractional) overlap
with Range(H). Then substitute Domain(H) for X in Domain(G). The result is
the value to be used for Domain(F).
\eh
This rule is a second-order correction to the previous one. If there is
no absolute equality, then a large intersection will suffice. Notice that
F may no longer be defined on all of its domain, even if G and H are.
If identical equality is taken as the maximum possible overlap betwen two
concepts, then this rule can be used to replace the preceding one completely.
\bh
\hh When trying to fill in the Isa entries for a composition F=G$\circ$H,
Examine G.Isa and H.Isa, and especially their intersection. Some of those
concepts may also claim F as an example. Run their definition facet to see.
\eh
To see how this is encoded into LISP, see Appendix 1.2.
\bh
\hh When trying to fill in the Genl or Spec entries for a composition F=G$\circ$H,
Examine the corresponding facet on G and on H.
\eh
This rule is similar to the preceding one, but wasn't as useful or as reliable.
\bh
\hh A satisfactory initial guess at the Worth value of composition F=G$\circ$H is
$\sqrt{G.Worth↑2 + H.Worth↑2}$.
\eh
\bh
\hh To fill in examples of F, where F=G$\circ$H, and both G and H are time-consuming,
but where many examples of both G and H exist,
Seek an example x$\→$y of H, and an example y$\→$z of G, and then return x$\→$z as a
probable example of F.
\eh
Above, `seek' is done in a tight, efficent manner. The examples
x$\→$y of H are hashed
into an array, based on the values y of each one. Then the arguments of the examples
of G are hashed to see if they occur in this array. Those that do will generate
an example of the new composition.
\bh
\hh To fill in examples of F, where F=G$\circ$H, and G is timeconsuming,
but many examples of G exist,
and it is not known whether H is time-consuming or not,
Spend a moment trying to access or trivially fill in examples of H.
If this succeeds, apply the preceding rule.
If this fails, then formally propose that AM fill in examples of H,
with priority equal to that of the current task, for these two reasons:
(i) if examples of H existed, then AM could have used the heuristic preceding
this one, to fill in examples of F, and (ii) it is dangerous to spend a long time
dealing with G$\circ$H before any examples at all of H are known.
\eh
This rule is of course tightly coupled to the preceding one.
The same rule exists for the case where just H is time-consuming, instead of G.
\bh
\hh When trying to fill in Conjecs about a composition F=G$\circ$H,
Consider that F may be the same as G (or the same as H).
\eh
It was somewhat depressing that this `stupid' heuristic turned out to be
valuable, perhaps even necessary for AM's top performance.
\hs{Composition}{Check}
\bh
\hh Check that F$\circ$G is really not the same as F, or the same as G.
Spend some time checking whether F$\circ$G is equivalent to any already-known active
concept.
\eh
This happens often enough to make it worth stating explicitly. Often, for example,
F will not even bother looking at the result of G! For example,
\ctrline{Proj2$\circ$Square(x,y) = Proj2(Square(x),y) = y = Proj2(x,y).}
\bh
\hh When checking the Algorithms entries for a composition F=G$\circ$H,
If range(H) is not wholly contained in the domain of G,
then the algorithm must contain a ``legality" check, ensuring that H(x) is a valid
member of the domain of G.
\eh
\hs{Composition}{Suggest}
\bh
\hh Given an interesting operation F:A$↑n\,\→\,$A,
consider composing F with itself.
\eh
This may result in more than one new operation. From F=division,
for example, we get the two operations (x/y)/z and x/(y/z).
AM quickly realizes that such variants are really equivalent,
and (if prodded) eventually realizes that F(F(x,y),z)=F(x,F(y,z)) is a common
situation (which we call associativity of F).
\bh
\hh If the newly-formed domain of the composition F=G$\circ$H contains more
than one occurrence of the concept D, and this isn't true of G or H,
Then consider creating a new operation, a specialization of F,
by Coalescing the domain/range of F, by eliminating one of the D components.
\eh
Thus when Insert$\circ$Delete is formed, the old Domain/range entries were
both of the form <Anything Struc\-ture $\→$ Struc\-ture>. The newly-created entry
for Insert$\circ$Delete was <Anything Anything Struc\-ture $\→$ Struc\-ture>; i.e.,
take x, delete it from S, then insert y into S. The above rule had AM
turn this into a new operation, with domain/range <Anything Struc\-ture $\→$ Struc\-ture>,
which deleted x from S and the inserted the very same x back into S.
\hs{Composition}{Interest}
\bh
\hh A composition F=G$\circ$H is interesting if G and H are very interesting.
\eh
\bh
\hh A composition F=G$\circ$H is interesting if F has an interesting property
not possessed by either G or H.
\eh
\bh
\hh A composition F=G$\circ$H is interesting if F has most of the interesting properties
which are possessed by either G or H.
This is slightly reduced if both G and H possess the property.
\eh
\bh
\hh A composition F=G$\circ$H is interesting if F lacks any undesirable properties
true of G or H.
This is greatly increased if both G and H possess the bad property, unless
G and H are very closely related to each other (e.g., H=G,or H=G\inv).
\eh
The numeric impact of each of these rules was guessed at initially, and
has never needed tuning. Here is an area where ex\-peri\-men\-ta\-tion might prove
interesting.
\bh
\hh A composition F=G$\circ$H is interesting if F maps interesting subsets of domain(H)
into interesting subsets of range(G).
F is to be judged even
more interesting
if the image was not thought to be interesting until
after it was explicitly isolated and studied because of part 1 of this very rule.
\eh
Here, an ``interesting" subset of domain(H) is one so judged by In\-ter\-ests(do\-main(H)).
A completely different set of criteria will be used to judge the interestingness of
the resultant image under F. Namely, for that purpose, AM will ask
for range(G).Interest, and ripple outwards to look for related interest features.
\bh
\hh A composition F=G$\circ$H is interesting if F\inv maps interesting subsets of range(G)
into interesting subsets of domain(F).
This is even better if the preimage
wasn't hitherto realized as interesting.
\eh
This is the converse of the preceding rule. Again, ``interesting" is judged by two
different sets of criteria.
\bh
\hh A composition F=G$\circ$H is interesting if F maps interesting elements of domain(H)
into interesting subsets of range(G).
\eh
\bh
\hh A composition F=G$\circ$H is interesting if F\inv maps interesting elements of range(G)
into interesting subsets of domain(F).
This is even better if the subset is only now seen to be interesting.
\eh
This is the analogue of an earlier rule, but for individual items rather
than for whole subsets of the domain and range of F.
\bh
\hh A composition F=G$\circ$H is interesting if range(H) is equal to, not just intersects,
one component of domain(G).
\eh
\bh
\hh A composition F=G$\circ$H is mildly interesting if range(H) is a specialization of
one component of domain(G).
\eh
This is a weakened version of the preceding feature. Such a composition is interesting
because it is guaranteed to always be applicable. If Range(H) merely intersects
a domain component of G, then there must be an extra check, after computing
H(x), to ensure it lies within the legal domain of G, before trying to run G on that
new entity H(x).
\bh
\hh A composition F=G$\circ$H is more interesting if range(G) is equal to a domain component
of H.
\eh
This is over and above the slight boost given to the composition because
it is an \4operation\0
whose domain
and range coincide (see rule 211).
\ASSEC{Heuristics for dealing with any Insertions}
\hs{Insertion}{Check}
\bh
\hh When checking an example of any kind of insertion of x into S,
Ensure that x is a member of S.
\eh
The only types of insertions known to AM are \4unconditional\0 insertions,
so this rule is valid. It is useful for ensuring that a particular new operation
really is an insertion-operation after all!
\ASSEC{Heuristics for dealing with the operation Coalesce}
\hs{Coalesce}{Fillin}
\bh
\hh When coalescing F(a,b,c,$\ldots $), whose domain/range is
<A B C$\ldots \ \→$
R>,
A good choice of two domain components to coalesce is a pair of
identically equal ones. Barring that, choose a pair related by
specialization (eliminate the more general one). Barring that, choose
a pair with a common specialization S, and replace both by S.
\eh
Thus to coalesce the operation ``Insert$\circ$Delete" [which takes two
items and a struc\-ture, deletes the first argument from the struc\-ture
and then inserts the second argument], AM examines its Domain/range
entry: <Anything Anything Struc\-ture $\→$ Struc\-ture>. Although it would
be legal to collapse the second and third arguments, the above rule
says it makes more sense in general to collapse the first and second.
In fact, in that case, AM gets an operation which tells it something
about multiple elements struc\-tures.
\bh
\hh When filling in Algorithms for a coalesced version G of active
concept F,
One natural algorithm is simply to call on F.Algs, with two arguments
the same.
\eh
Of course the two identical arguments are those which have been
decided to be merged. This will be decided before the definition and
algorithm facets are filled in. Thus a natural algorithm for Square
is to call on TIMES.Alg(x,x). The following rule is similar:
\bh
\hh When filling in Definitions for a coalesced version G of active
concept F,
One natural Definition is simply to call on F.Defn, with two
arguments the same.
\eh
\bh
\hh When filling in the Worth of a new coalesced version of F,
A suitable value is 0.9$\cdot $(Worth of F) + 0.1$\cdot $(Worth of Coalesce).
\eh
This is a compromise between (i) the knowledge that the new operation
will probably be less interesting than F, and (ii) the knowledge that
it may lead to even more valuable new concepts (e.g., \4its\0 inverse
may be more interesting than F's). The formula also incorporates a
small factor which is based on the overall value of coalescings which
AM has done so far in the run.
\hs{Coalesce}{Check}
\bh
\hh If G and H are each two coalescings away from F, for any F,
Then check that G and H aren't really the same, by writing their
definitions out in terms of F.Defn.
\eh
Thus if R(a,b,c) is really F(a,b,a,c), and S(a,b,c) is really
F(a,b,c,c), and R and S get coalesced again, into G(a,b) which is
R(a,b,a) and into H(a,b) which is S(a,b,a), then both G and H are
really F(a,b,a,a). The order of coalescing is unimportant. This is
a boost to the more general impetus for checking this sort of thing,
rule 22. This rule is faster, containing a special-purpose
program for untangling argument-calls rapidly. If the concept of
Coalesce is excised from the system, one can easily imagine it being
re-derived by a more general `coincidence' strategy, but how will
these specific, high-powered, tightly-coded heuristics ever get
discovered and tacked onto the Coalesce concept? This is an instance
of the main meta-level research problem proposed earlier in the
book (Chapter 7).
\hs{Coalesce}{Suggest}
\bh
\hh If a newly-interesting active concept F(x,y) takes a pair of N's
as arguments,
Then create a new concept, a specialization of F, called F-Itself,
taking just one N as argument, defined as F(x,x), with initial worth
Worth(F).
If AM has never coalesced F before, this gets a slight bonus value.
If AM has coalesced F before, say into S, then modify this
suggestion's value according to the current worth of S.
The lower the system's interest-threshhold is, the more attactive
this suggestion becomes.
\eh
AM used this rule to coalesce many active concepts. Times(x,x) is
what we know as squaring; Equality(x,x) turned out to be the constant
predicate True; Intersect(x,x) turned out to be the identity
operator; Compose(f,f) was an interesting ``iteration" operator\foo{
e.g., Compose(Compose,Compose) is an operator which takes 3
operations f,g,h and forms ``f$\circ $g$\circ $h"; i.e., their joint composition.
}; etc. This rule is really a bundle of little meta-rules
modifying one suggestion: the suggestion that AM coalesce F. The
very last part of the above rule indicates that if the system is
desparate, this is the least distasteful way to ``take a chance" on a
high-payoff high-risk course of action. It is more sane than, e.g.,
randomly composing two operations until a nice new one is created.
\bh
\hh If concept F takes only one argument,
Then it is not worthwhile to try to coalesce it.
\eh
This rule was of little help cpu-timewise, since even if AM tried to
coalesce such an active concept,it would fail almost instantaneously.
The rule did help make AM appear smarter, however.
\ASSEC{Heuristics for dealing with the operation Canonize}
\hs{Canonize}{Fillin}
\bh
\hh If the task is to Canonize predicates P1 and P2 (over A$\times $A)\foo{ That
is, find a function F such that P1(x,y) iff P2(F(x),F(y)). }, and the
difference between a definition of P1 and definition of P2 is just
that P2 performs some extra check that P1 doesn't,
Then F should convert any $a\epsilon \,$A into a member of A which automatically
satisfies that extra constraint.
\eh
Thus when P1=Same-length, P2=Equality, A=Lists, the extra constraint
that P2 satisfies is just that it recurs in the CAR direction: the
CARs of the two arguments must also satisfy P2. P1 doesn't have such
a requirement. The above rule then has AM seek out a way to guarantee
that the CARs will always satisfy Equality. A special hand-crafted
piece of knowledge tells AM that since ``T=T" is an example of
Equality, one solution is for all the CARs to be the atom T. Then the
operation F must contain a procedure for converting each member of a
struc\-ture to the atom ``T". Thus (A C $\{$Z A B$\}$ Q Q) would be
converted to (T T T T T). This rule is a specialized, ``compiled"
version of the idea expressed in rule number 101.
\bh
\hh If the task is to Canonize P1 and P2 over A$\times $A, trying to
synthesize F, where A=Struc\-ture,
Then perhaps there is a distinguished type of struc\-ture B which the
argument to F should always be converted into. In that case,
consider P1 and P2 as two predicates over B$\times $B.
\eh
This special-purpose rule is used to guide a series of experiments,
to determine whether P1 is affected by adding multiple copies of
existing elements into its arguments, and whether its value is
affected by rearranging some of its arguments' elements. In the case
of P1=Same-size, the answers are: multiple elements do make a
difference, but rearrangement doesn't. So the canonical type of
struc\-ture for F=Size must be one which is Mult-eles-allowed and also
one which is Unordered. Namely, a Bag. Thus F is modified so that it
first converts its argument to a Bag. Then Equality and Same-size
are viewed as taking a pair of Bags, and Size is viewed as taking one
Bag and giving back a canonical bag.
\bh
\hh After F is created from P1 and P2, as Canonize(P1,P2),
an acceptable value for the worth of F is the maximum of the worths
of P1 and P2.
\eh
In the actual Lisp code, an extra small term is added which takes
into account the overall value of all the Canonizations which AM has
recently produced.
\bh
\hh If the current task has just created a canonical specialization B
of concept A, with respect to predicates P1 and P2, [i.e., two
members of B satisfy P1 iff they satisfy P2],
Then add the following entry to the Analogies facet of B:
\hjust{\hskip 50pt A $↔$ B}
\hjust{\hskip 47pt P1 $↔$ P2}
\hjust{\hskip 22pt Operations-on-and-into(A) $↔$ Those operations restricted to B's}
\eh
This rather incoherent rule says that it's worth taking the trouble
to study the behavior of each operation when it is restricted to
working on standard or ``canonical" items. Moreover, some of the old
relationships may carry over --- or at least have analogues --- in this
restricted world. When numbers are discovered as canonical bags, all
the bag operations are restricted to work on only canonical bags, and
they startlingly turn into what we know and love as numeric operations.
Many of the old bag-theoretic relationships have numeric analogues.
Thus we knew that the bag-difference of x and x was the empty bag;
this is still true for x a canonical bag, but we would word it as ``x
minus x is zero". This is because the restriction of Bag-difference
to canonical bags (bags of T's) is precisely the operation we call
subtraction.
\bh
\hh When Canonize works on P1, P2 (two predicates), and produces an
operation, F,
Both predicates must share a common Domain, of the form A$\times $A for some
concept A, and the new operation F can have <A $\→$ A> as one of its
Domain/range entries.
If a canonical specialization (say `B') of A is defined, then the
domain/range of F can actually be tightened to <A $\→$ B>, and it is
also worth explicitly storing the redundant entry <B $\→$ B>.
\eh
\bh
\hh In the same situation as the last rule,
One conjecture is that P1 and P2 are equal, when restricted to
working on pairs of B's [i.e., pairs of Canonical A's, A's which are
in F(A), range items for F, items x which are the image F(a) of some
a$\epsilon \,$A].
\eh
After canonizing Equal and Same-size into the new operation Length,
AM conjectures that two canonical bags are equal iff they have the
same size.
\hs{Canonize}{Suggest}
\bh
\hh When Canonize works on P1, P2, both predicates over A$\times $A, and
produces an operation F:A$→$A,
It is worth defining and studying the image F(A); i.e., the totality
of A's which are canonical, already in standard form. When this new
concept Canonical-A is defined, suggest the task ``Fillin Dom/range
entries for Canonical-A".
\eh
Thus AM studied Canonical-Bags, which turned out to be isomorphic to
the natural numbers. What we've called `Canonical-A' in this rule,
we've referred to simply as `B' in earlier Canonizing rules.
\bh
\hh If P1 is a very interesting predicate over A$\times $A, for some
interesting concept A,
Then look over P1.Spec for some other predicate P2 which is also over
A$\times $A, and which has some interesting properties P1 lacks. For each
such predicate P2, consider applying Canonize(P1,P2).
\eh
\bh
\hh After producing F as Canonize(P1,P2) [both predicates over A$\times $A],
and after defining Canonical-A,
It is worth restricting operations in In-dom-of(A) to Canonical-A.
Some new properties may emerge.
\eh
Thus after defining Canonical-Bags, AM looked at Bags.In-dom-of. In
that list was the operation ``Bag-union". So AM considered the
restriction of Bag-union to Canonical-bags. Instead of Bag-union
mapping two bags into a new bag, this new operation took two
canonical-bags and mapped them into a new bag. AM later noticed that
this new bag was itself always canonical. Thus was born the operation
we call ``Addition".
\bh
\hh After Canonical-A is produced,
It is marginally worth trying to restrict operations in
In-range-of(A) to map into Canonical-A.
\eh
This gives an added boost to picking Union to restrict, since it is
in both Bags.In-dom-of and Bags.In-ran-of. This rule is much harder
to implement, since it demands that the range be restricted. There
are just a few special-purpose tricks AM knows to do this.
Restricting the domain is, by comparison, much cleaner. AM simply
creates a new concept with the same definition, but with a more
restricted domain/range facet. For restricting the range, AM must
insert into the definition a check to ensure that the final result is
inside Canonical-A, not just in A. This leads to a very inefficent
definition.
\bh
\hh After Canonical-A is produced,
It is worthwhile to consider filling in examples (especially
boundary) of that new concept.
\eh
This is above and beyond the slight push which rule 111 gives
that task.
\ASSEC{Heuristics for dealing with the operation Substitute}
Note that substitution operations are produced via the initial
concepts called Parallel-replace and Parallel-replace2. The following
rules are tacked on there.
\hs{Parallel-replace}{Suggest}
\bh
\hh If two different variables are used to represent the same
entity,\foo{ When we say that x and y represent the same entity, what we
really mean is that they have the same domain of identity (e.g.,
$\forall x \epsilon \,$Bags) and they are equally free (there is a precise logical
definition of all this, but there is little point to presenting it
here.) } then substitute one for the other.
This is very important if the two occurrences are within the same
entry on some facet of a single concept, and less so otherwise.
The dominant variable should be the one typed out previously to the
user; barring that, the older usage; barring that, the one closest to
the letter {\bf ``a" } in the alphabet.
\eh
This heuristic was used less often --- and proved less impressive ---
than was originally anticipated by the author. Since most concepts
were begotten from older ones, they always assumed the same variable
namings, hence there were very few mismatches. A special test was
needed to explicitly check for ``x=y" occurring as a conjunct
somewhere, in which case we removed it and substituted y for x
throughout the conjunction.
\bh
\hh If two expressions (especially: two conjectures) are struc\-turally
similar, and appear to differ by a certain substitution,
Then if the substitution is permissable we have just arrived at the
same expression in various ways, and tag it as such,
But if the substitution is not seen to be tautologous, then a new
analogy is born. Associate the constituent parts of both expressions.
This is made interesting if there are several concepts involved which
are assigned new analogues.
\eh
The similar statements of the associativity of Add and Times led to
this rule's identifying them as analogous. If AM had been more
sophisticated, it might have eventually formulated some abstract
algebra concepts like ``semigroup" from such analogies.
\ASSEC{Heuristics for dealing with the operation Restrict}
\hs{Restrict}{Fillin}
\bh
\hh When filling in definitions (algorithms) for a restriction R of
the active concept F,
One entry can simply be a call on F.Defn (F.Algs).
\eh
Thus one definition of Addition will always be as a call on the old,
general operation `Bag-union.' Of course one major reason for
restricting the domain/range of an activity is that it can be
performed using a faster algorithm! So the above rule was used
frequently if not dramatically.
\bh
\hh When creating a restriction R of the active concept F,
Note that R.Genl should contain F, and that F.Spec should contain R.
\eh
\bh
\hh When creating in a restriction R of the active concept F, by
restricting the domain or range to some specialization S of its
previous value C,
A viable initial guess for R.Worth is F.Worth, augmented by the
difference in worth between S and C. Hopefully, S.Worth is bigger
than C.Worth!
\eh
\ASSEC{Heuristics for dealing with the operation Invert}
\hs{Invert}{Fillin}
\bh
\hh When filling in definitions for an Inverse F\inv of the active
concept F,
One ``Sufficent Defn" entry can simply be a blind search through the
examples of F.
\eh
If we already knew that 4$\→$16 is an example of Square, then AM can use
the above rule to quickly notice that Square-Inverse.Defn(16,4) is
true. This is almost the ``essence" of inverting an operation, of
course.
\hs{Invert}{Suggest}
\bh
\hh After creating an inverted form F\inv of some operation F,
If the only definition and algorithm entries are the ``obvious"
inefficient ones,
Then consider the task: ``Fill in algorithms for F\inv``, because the
old blind search is just too awful to tolerate.
\eh
\ASSEC{Heuristics for dealing with Logical combinations}
Eventually, there may be separate concepts for each kind of logical
connective. For the moment, all Boolean operators are lumped together
here. Their definition is too trivial for a `Fillin' heuristic to be
useful, and even `Check' heuristics are almost pointless.
\hs{Logical-combine}{Check}
\bh
\hh The user may sometimes indicate `Conjunction' when he really means
`Repeating'.
\eh
\hs{Logical-combine}{Suggest}
\bh
\hh If there is something interesting to say about entities satisfying
the disjunction (conjunction) of two concepts' definitions,
Then consider creating a new concept defined as that logical
combination of the two concepts' definitions.
\eh
\bh
\hh Given an implication,
Try to weaken the left side as much as possible without destroying
the validity of the whole implication. Similarly, try to strengthen
the right side of the implication.
\eh
\hs{Logical-combine}{Interest}
\bh
\hh A disjunction (conjunction) is interesting if there is a
conjecture which is very interesting yet which cannot be made about
any one disjunct (conjunct).
\eh
In other words, their logical combination implies more than any
consituent.
\bh
\hh An implication is interesting if the right side is more
interesting than the left side.
\eh
\bh
\hh An implication is interesting if the right side is interesting yet
unexpected based only on assuming the left side.
\eh
\ASSEC{Heuristics for dealing with Struc\-tures}
\hs{Struc\-ture}{Fillin}
\bh
\hh To fill in examples of a kind of struc\-ture S,
Start with an empty S, pluck any other member of Examples(Struc\-ture),
and transfer members one at a time from the random struc\-ture into the embryonic S.
Finally, check that the resultant S really satisfies S.Defn.
\eh
This is useful, e.g., to convert examples of lists into examples of sets.
\bh
\hh To fill in specializations of a kind of struc\-ture,
add a new constraint that each member must satisfy,
or a constraint on all pairs of members,
or a constraint on all pairs of distinct members,
or a constraint which the struc\-ture as a whole must satisfy.
Such a constraint is often merely a stipulation of being an example of an X,
for some interesting concept X.
\eh
Thus AM might specialize Bags into Bags-of-primes,
or into Bags-of-distinct-primes, or into Bags-containing-a-prime.
\hs{Struc\-ture}{Interest}
\bh
\hh Struc\-ture S is mildly interesting if all members of S satisfy the interesting
predicate P, or (equivalently) if they are all accidentally examples of
the interesting concept C, or (similarly) if all pairs of members of S
satisfy the interesting binary predicate P, etc.
Also: a {\it kind} of struc\-ture is interesting if it appears that each instance of
such a struc\-ture satisfies the above condition (for a fixed P or C).
\eh
Thus a singleton is interesting because all pairs of members satisfy Equal.
The concept ``Singletons" is interesting because each singleton is mildly
interesting in just that same way.
Similarly, AM defines the concept of a bag containing only primes,
because the above rule says it might be interesting.
\bh
\hh A struc\-ture is mildly interesting if one member is very interesting.
Even better: exactly one member.
Also: a {\it kind} of struc\-ture is interesting if each instance satisfies the
above condition in the same way.
\eh
Thus the values of ADD\inv are interesting because they always contain
precisely one bag which is a Singleton.
\ASSEC{Heuristics for dealing with Ordered-struc\-tures}
\hs{Ordered-struc}{Fillin}
\bh
\hh To fill in some new examples of the ordered struc\-ture S, when some
already exist,
Pick an existing example and randomly permute its members.
\eh
\bh
\hh To fill in specializations of a kind of ordered struc\-ture,
add a new constraint that each pair of adjacent members must satisfy,
or a constraint on all ordered pairs of members in the order they
appear in the struc\-ture. Such a constraint is often merely a
stipulation of being an example of an X, for some interesting concept
X.
\eh
Thus Lists-of-numbers might be specialized into
Sorted-lists-of-numbers, assuming AM has discovered ``$≤$" and assuming
it is chosen as the `constraint' relationship between adjacent
members of the list.
\hs{Ordered-struc}{Check}
\bh
\hh If the struc\-ture is to be accessed sequentially until some
condition is met, and if the precise ordering is superfluous,
Then keep the struc\-ture ordered by frequency of use, the most useful
element first.
\eh
This is a simple data-struc\-ture management trick. If you have several
rules to use in a certain situation, and rule R is one which usually
succeeds, then put R first in the list of rules to try. Similarly, in
a pattern-matcher, try first the test most likely to detect
non-matching arguments.
\bh
\hh If struc\-ture S is always to be maintained in alphanumeric order,
Then AM can\foo{ due to the current LISP implementation of
data-struc\-tures } actually maintain it as an unordered struc\-ture, if
desired.
\eh
Luckily this heavily implementation-dependent rule was never needed
by AM.
\hs{Ordered-struc}{Interest}
\bh
\hh An ordered struc\-ture S is interesting if each adjacent pair of
members of S satisfies predicate P (for some rare, interesting P).
\eh
When AM discovers the relation ``$≤$", it immediately thinks that any
\4sorted\0 list of numbers is more interesting, due to the above
rule.
\ASSEC{Heuristics for dealing with Unordered-struc\-tures}
\hs{Unord-struc}{Check}
\bh
\hh To check an example of an unordered struc\-ture,
Ensure that it is in alphanumerically-sorted order. If not, then {\it Sort}
it.
\eh
All unordered objects are maintained in lexicographic order, so that
two of them can be tested for equality using the LISP function EQUAL.
Because of this convention, any two struc\-tures can therefore be
tested for equality using this fast list-struc\-ture comparator.
\ASSEC{Heuristics for dealing with Multiple-eles-struc\-tures}
\hs{Mult-ele-struc}{Fillin}
\bh
\hh To fill in some new examples of the struc\-ture S, where S is a
struc\-ture admitting multiple occurrences of the same element, when
some examples already exist,
Pick an existing example and randomly change the multiplicity with
which various members occur within the struc\-ture.
\eh
\ASSEC{Heuristics for dealing with Sets}
\hs{Sets}{Suggest}
\bh
\hh If P is a very interesting predicate over X,
Then study these two sets: the members of X for which P holds, and
the ones for which P fails.
\eh
While we humans know that this partitions X into two pieces, AM is never
explicitly told this. It would occasionally be surprised to discover
that the union of two such complements ``accidentally" coincided with
X. Incidentally, this rule is really the key linkage between
predicates and sets; it is close to the entry on Set.View which tells
how to view any predicate as a set.
\hs{Sets}{Interest}
\bh
\hh A set S is interesting if, for some interesting predicate P, whose
domain is X,
S accidentally appears to be related strongly
to $\{x \epsilon \, X \ | \ P(x)\}$, i.e.,
to those members of X satisfying P.
\eh
To the surprise of the author, this rule was not at all important
to AM's behavior.